gc_essen.c

#include <stdio.h>
#include <stdlib.h>

// http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/

#define GC_STACK_MAX 256

enum gc_object_type {
    GC_OBJ_INT,
    GC_OBJ_PAIR,
};

struct gc_object {
    enum gc_object_type type;
    unsigned char marked;

    /* The next object in the linked list of heap allocated objects. */
    struct gc_object* next;

    union {
        /* GC_OBJ_INT */
        int value;

        /* GC_OBJ_PAIR */
        struct {
            struct gc_object* head;
            struct gc_object* tail;
        };
    };
};

struct gc_vm {
    struct gc_object* stack[GC_STACK_MAX];
    int stackSize;

    /* The first object in the linked list of all objects on the heap. */
    struct gc_object* firstObject;

    /* The total number of currently allocated objects. */
    int numObjects;

    /* The number of objects required to trigger a GC. */
    int maxObjects;
};

void gc_assert(int condition, const char* message) {
    if (!condition) {
        printf("%s\n", message);
        exit(1);
    }
}

struct gc_vm* gc_new_vm(void) {
    struct gc_vm* vm = (struct gc_vm*) calloc(1, sizeof(struct gc_vm));
    vm->stackSize = 0;
    vm->firstObject = NULL;
    vm->numObjects = 0;
    vm->maxObjects = 8;
    return vm;
}

void gc_push(struct gc_vm* vm, struct gc_object* value) {
    gc_assert(vm->stackSize < GC_STACK_MAX, "Stack overflow!");
    vm->stack[vm->stackSize++] = value;
}

struct gc_object* gc_pop(struct gc_vm* vm) {
    gc_assert(vm->stackSize > 0, "Stack underflow!");
    return vm->stack[--vm->stackSize];
}

void gc_mark(struct gc_object* object) {
    /* If already marked, we're done. Check this first to avoid recursing
    on cycles in the object graph. */
    if (object->marked) return;

    object->marked = 1;

    if (object->type == GC_OBJ_PAIR) {
        gc_mark(object->head);
        gc_mark(object->tail);
    }
}

void gc_mark_all(struct gc_vm* vm) {
    int i;
    for (i = 0; i < vm->stackSize; i++) {
        gc_mark(vm->stack[i]);
    }
}

void gc_sweep(struct gc_vm* vm) {
    struct gc_object** object = &vm->firstObject;
    while (*object) {
        if (!(*object)->marked) {
            /* This object wasn't reached, so remove it from the list and free it. */
            struct gc_object* unreached = *object;

            *object = unreached->next;
            free(unreached);

            vm->numObjects--;
        } else {
            /* This object was reached, so unmark it (for the next GC) and move on to
            the next. */
            (*object)->marked = 0;
            object = &(*object)->next;
        }
    }
}

void gc_run(struct gc_vm* vm) {
    int numObjects = vm->numObjects;

    gc_mark_all(vm);
    gc_sweep(vm);

    vm->maxObjects = vm->numObjects * 2;

    printf("Collected %d objects, %d remaining.\n", numObjects - vm->numObjects,
        vm->numObjects);
}

struct gc_object* gc_new_object(struct gc_vm* vm, enum gc_object_type type) {
    struct gc_object* object;
    if (vm->numObjects == vm->maxObjects) {
        gc_run(vm);
    }
    object = (struct gc_object*) calloc(1, sizeof(struct gc_object));
    object->type = type;
    object->next = vm->firstObject;
    vm->firstObject = object;
    object->marked = 0;

    vm->numObjects++;

    return object;
}

void pushInt(struct gc_vm* vm, int intValue) {
    struct gc_object* object = gc_new_object(vm, GC_OBJ_INT);
    object->value = intValue;

    gc_push(vm, object);
}

struct gc_object* pushPair(struct gc_vm* vm) {
    struct gc_object* object = gc_new_object(vm, GC_OBJ_PAIR);
    object->tail = gc_pop(vm);
    object->head = gc_pop(vm);

    gc_push(vm, object);
    return object;
}

void objectPrint(struct gc_object* object) {
    switch (object->type) {
    case GC_OBJ_INT:
        printf("%d", object->value);
        break;

    case GC_OBJ_PAIR:
        printf("(");
        objectPrint(object->head);
        printf(", ");
        objectPrint(object->tail);
        printf(")");
        break;
    }
}

void freeVM(struct gc_vm *vm) {
    vm->stackSize = 0;
    gc_run(vm);
    free(vm);
}

void test1() {
    struct gc_vm* vm;
    printf("Test 1: Objects on stack are preserved.\n");
    vm = gc_new_vm();
    pushInt(vm, 1);
    pushInt(vm, 2);

    gc_run(vm);
    gc_assert(vm->numObjects == 2, "Should have preserved objects.");
    freeVM(vm);
}

void test2() {
    struct gc_vm* vm;
    printf("Test 2: Unreached objects are collected.\n");
    vm = gc_new_vm();
    pushInt(vm, 1);
    pushInt(vm, 2);
    gc_pop(vm);
    gc_pop(vm);

    gc_run(vm);
    gc_assert(vm->numObjects == 0, "Should have collected objects.");
    freeVM(vm);
}

void test3() {
    struct gc_vm* vm;
    printf("Test 3: Reach nested objects.\n");
    vm = gc_new_vm();
    pushInt(vm, 1);
    pushInt(vm, 2);
    pushPair(vm);
    pushInt(vm, 3);
    pushInt(vm, 4);
    pushPair(vm);
    pushPair(vm);

    gc_run(vm);
    gc_assert(vm->numObjects == 7, "Should have reached objects.");
    freeVM(vm);
}

void test4() {
    struct gc_vm* vm;
    struct gc_object* a, *b;
    printf("Test 4: Handle cycles.\n");
    vm = gc_new_vm();
    pushInt(vm, 1);
    pushInt(vm, 2);
    a = pushPair(vm);
    pushInt(vm, 3);
    pushInt(vm, 4);
    b = pushPair(vm);

    /* Set up a cycle, and also make 2 and 4 unreachable and collectible. */
    a->tail = b;
    b->tail = a;

    gc_run(vm);
    gc_assert(vm->numObjects == 4, "Should have collected objects.");
    freeVM(vm);
}

void perfTest() {
    struct gc_vm* vm;
    int i;
    printf("Performance Test.\n");
    vm = gc_new_vm();

    for (i = 0; i < 1000; i++) {
        int j, k;
        for (j = 0; j < 20; j++) {
            pushInt(vm, i);
        }

        for (k = 0; k < 20; k++) {
            gc_pop(vm);
        }
    }
    freeVM(vm);
}

#if defined(_MSC_VER)
#ifndef _CRTDBG_MAP_ALLOC
#define _CRTDBG_MAP_ALLOC
#endif // _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>
#define MEM_CHECK_BEGIN() do { _CrtSetDbgFlag( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF ); } while(0)
#define MEM_CHECK_DUMP_LEAKS() do { _CrtDumpMemoryLeaks(); } while(0)
#else
#define MEM_CHECK_BEGIN() do { ; } while ( 0 )
#define MEM_CHECK_DUMP_LEAKS() do { ; } while ( 0 )
#endif

int main(int argc, const char * argv[]) {
    MEM_CHECK_BEGIN();

    test1();
    test2();
    test3();
    test4();
    perfTest();

    MEM_CHECK_DUMP_LEAKS();

    return 0;
}