libtreadmill

An implementation of Baker's Treadmill Garbage Collector.

Baker's Treadmill is an incremental, non-moving GC algorithm, trivially made real-time. Read about the algorithm in this article.

Why?

This library is used by TerrorVM, a Virtual Machine for dynamic languages, and was extracted from it to keep the project modular and the interface clear.

Using it in your project

Installing it as a submodule

$ cd <your_project>
$ mkdir -p deps
$ git submodule add git://github.com/txus/libtreadmill deps/libtreadmill

In your Makefile, add this to your CFLAGS:

CFLAGS=<whatever> -Ideps/libtreadmill/include

And this to your LDFLAGS:

LDFLAGS=<whatever> deps/libtreadmill/build/libtreadmill.a

Create a gc target in your Makefile:

gc:
$(MAKE) -C deps/libtreadmill

And finally add it as a dependency of your main target:

all: gc <your> <other> <targets>

Done! :)

Interface

libtreadmill interfaces with your project in two points: your objects (or values or however you call them) and some kind of state (to figure out the rootset).

As easily seen in the tests, here's an example State and Object structs:

typedefstructstate_s {
TmStateHeadergc;
... // your own things
} State;
typedefstructobject_s {
TmObjectHeadergc;
... // your own things
} Object;

The first element in both structs must be a TmStateHeader for the state and a TmObjectHeader for the object.

Interface with the State

Whenever you initialize a State object, you have to give it a TmRootsetFn function pointer, which will accept a pointer to a TmStateHeader and return a pointer to a Tm_DArray (a dynamic array used by libtreadmill), and implement the function, like this for example:

#include<treadmill/gc.h>#include<treadmill/darray.h>staticinlineTm_DArray*get_rootset(TmStateHeader*state_header)
{
// Create the dynamic array that we'll returnTm_DArray*rootset=Tm_DArray_create(sizeof(TmObjectHeader*), 10);
// Typecast to our own State structState*state= (State*)state_header;
/* * From the state, figure out the rootset, and for each object, do this: * Tm_DArray_push(rootset, object); */returnrootset;
}
State*State_new()
{
State*state=calloc(1, sizeof(State));
// Assign the function state->gc.rootset=get_rootset;
returnstate;
}

Interface with your objects

As we've seen, an object's first element is a TmObjectHeader. The Treadmill needs to know three things about your objects: their size, how to release them, and how to scan their pointers to other objects.

To let the Treadmill know about the first, it's as easy as sizeof(Object).

Regarding how to release them, there's a function pointer for that. An example implementation would be:

voidrelease_my_object(void*value)
{
// call your own Object_destroy function or whateverObject_destroy((Object*)value);
}

Regarding how to scan their pointers, there's another function pointer for that, with this example implementation:

voidscan_my_pointers(TmHeap*heap, TmObjectHeader*object, TmCallbackFncallback)
{
// Typecast to your own Object typeObject*self= (Object*)object;
/* * Figure out the `self` points to:, and for each `obj` of them, do this: * callback(heap, (TmObjectHeader*)obj); */
}

You're all set! This is all the Treadmill needs to know about your objects.

Creating, using and destroying the Heap

To initialize the heap, do this:

TmHeap*heap=TmHeap_new(
(TmStateHeader*)state, // your initialized state object1000, // initial size of the heap1500, // growth rate in number of cells200, // scan every 200 allocationssizeof(Object), // the size of your Objectsrelease_my_object, // a pointer to your release functionscan_my_pointers// a pointer to your function to scan pointers
);

Keep a reference to the heap wherever you deem best. Every time you need to allocate an object, do this:

Object*my_obj= (Object*)Tm_allocate(heap);

And finally, at the end of your program, remember to destroy the heap:

TmHeap_destroy(heap);

Development

To build libtreadmill and run its test suite:

$ git clone git://github.com/txus/libtreadmill
$ cd libtreadmill
$ make

Contributing

1. Fork it
2. Create your feature branch (git checkout -b my-new-feature)
3. Commit your changes (git commit -am 'Added some feature')
4. Push to the branch (git push origin my-new-feature)
5. Create new Pull Request