Toy GC
For a project I'm considering, I took a few hours to see if I could write a working garbage collector.
This is a very bare-bones copying GC, written without any reference to How To Do It Properly (just my knowledge of how a copying GC works, but I believe it is mostly cleanly written other than (a) the hardcoded pointer comparisons for object layouts, and (b) support for exactly one GC root, which happens to be the object at the lowest address. (It also calls a “heap” that which I believe is conventionally called a “space”. And I suppose someone could take issue with my placements of casts and void *s.)
The test program simply allocates a structure containing the strings “Hello” and “world”, allocates a bunch of junk, and then prints the strings to show that they are still intact.
#include // printf, fprintf #include // bool, true, false #include // exit #include // memset, strncpy // --- A few object types, with enough runtime type info for the GC to do its job. --- #define STRINGSIZE 6 struct type { size_t size; }; struct object { const struct type *type; }; struct string { struct object object; char data[STRINGSIZE]; }; const struct type string_type = {sizeof(struct string)}; struct cons { struct object object; struct object *car, *cdr; }; const struct type cons_type = {sizeof(struct cons)}; struct forward { struct object object; struct object *target; }; const struct type forward_type = {sizeof(struct forward)}; // --- The GC heap --- #define HEAPSIZE 50 #define HEAPS 2 #define OLD_ERASED_VALUE '@' #define NEW_ERASED_VALUE '$' static char heaps[HEAPS][HEAPSIZE]; static int current = 0; static char *low = heaps[0], *high = heaps[0 + 1], *allocator = heaps[0]; // --- The GC --- void *galloc(size_t size); struct object *gc_copy(struct object *const root) { if (root->type == &forward_type) { return ((struct forward *)root)->target; } // allocate new object struct object *copy = galloc(root->type->size); // copy contents copy->type = root->type; if (root->type == &string_type) { memcpy(copy, root, root->type->size); } else if (root->type == &cons_type) { ((struct cons *)copy)->car = gc_copy(((struct cons *)root)->car); ((struct cons *)copy)->cdr = gc_copy(((struct cons *)root)->cdr); } else { fprintf(stderr, "Unrecognized type!\n"); exit(EXIT_FAILURE); } // replace old with forwarding root->type = &forward_type; ((struct forward *)root)->target = copy; return copy; } void gc() { const int new = (current + 1) % HEAPS; const int old = current; fprintf(stderr, "[GC: switching to heap %i]\n", new); current = new; allocator = low = heaps[current]; high = heaps[current + 1]; memset(low, NEW_ERASED_VALUE, HEAPSIZE); if ((char *)gc_copy((struct object *)heaps[old]) != heaps[new]) { fprintf(stderr, "New GC root not at base of heap!\n"); exit(EXIT_FAILURE); } memset(heaps[old], OLD_ERASED_VALUE, HEAPSIZE); } void *galloc(size_t size) { if (size < forward_type.size) { fprintf(stderr, "Cannot allocate less than a forward (%li bytes)\n", (long)size); } if (high - allocator < size) { gc(); } if (high - allocator < size) { fprintf(stderr, "GC failed to make room for %li bytes\n", (long)size); exit(EXIT_FAILURE); } void *ptr = allocator; allocator += size; return ptr; } void *objalloc(const struct type *const type) { struct object *object = galloc(type->size); object->type = type; return object; } void *deref(void *const refptr) { if (((struct object *)refptr)->type == &forward_type) { fprintf(stderr, "Uncleaned forward!\n"); exit(EXIT_FAILURE); } return refptr; } #define DEREF(t,x) ((struct t *)deref(x)) void *root() { return heaps[current]; } // --- The test program --- int main(void) { objalloc(&cons_type); // root object is at the low address of the heap for (int i = 0; i < 5; i++) { struct string *lit1 = objalloc(&string_type); strncpy(lit1->data, "Hello", STRINGSIZE); DEREF(cons, root())->car = (struct object *)lit1; struct string *lit2 = objalloc(&string_type); strncpy(lit2->data, "world", STRINGSIZE); DEREF(cons, root())->cdr = (struct object *)lit2; for (int i = 0; i < 10; i++) { objalloc(&cons_type); } printf("%s %s\n", DEREF(string, DEREF(cons, root())->car)->data, DEREF(string, DEREF(cons, root())->cdr)->data); } return 0; }