ToyGC

marksweep.c

#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdarg.h>
#include <time.h>

#define i8 int8_t
#define i16 int16_t
#define i32 int32_t
#define i64 int64_t

#define u8 uint8_t
#define u16 uint16_t
#define u32 uint32_t
#define u64 uint64_t

#define f32 float
#define f64 double

#define usize size_t

static usize totalAlloc = 0;
static usize totalDealloc = 0;
static usize totalGCCalls = 0;
static usize totalGCTime = 0;

void *xmalloc(usize size) {
    totalAlloc++;
    return malloc(size);
}

void xfree(void *p) {
    totalDealloc++;
    free(p);
}

typedef struct arrHeader {
    usize len;
    usize cap;
    char buf[0];
} arrHeader;

#define _arrHeader(a) ((arrHeader *)((char *)(a)-offsetof(arrHeader, buf)))

#define arrLen(a) ((a) ? _arrHeader(a)->len : 0)
#define arrCap(a) ((a) ? _arrHeader(a)->cap : 0)
#define arrAppend(a, v) ((arrLen(a) == arrCap(a) ? (a) = arrGrow(a, sizeof(*a)) : 0), \
    (a)[_arrHeader(a)->len++] = (v))
#define arrFree(a) ((a) ? (xfree(_arrHeader(a)), (a) = NULL) : 0)

static void *arrGrow(const void *arr, usize elem_size) {
    if (!arr) {
        arrHeader *header = (arrHeader *)xmalloc(sizeof(arrHeader) + elem_size * 8);
        header->cap = 8;
        header->len = 0;
        return (void *)header->buf;
    }
    usize new_cap = arrCap(arr) * 2;
    usize new_size = new_cap * elem_size + offsetof(arrHeader, buf);
    arrHeader *header = realloc(_arrHeader(arr), new_size);
    header->cap = new_cap;
    return (void *)header->buf;
}

typedef enum objectType {
    OBJECT_TYPE_NUMERIC,
    OBJECT_TYPE_ARRAY,
} objectType;

typedef struct object {
    struct object *next;
    union {
        int numeric;
        struct object **array;
    } value;
    objectType type;
    bool mark;
} object;

void vmDebugf(const char *fmt, ...) {
#ifdef DEBUG
    va_list args;
    va_start(args, fmt);
    vprintf(fmt, args);
    va_end(args);
#endif
}

void objectMark(object *obj) {
    if (obj->mark) return;
    obj->mark = true;
    if (obj->type == OBJECT_TYPE_ARRAY) {
        for (u32 i = 0; i < arrLen(obj->value.array); i++) {
            objectMark(obj->value.array[i]);
        }
    }
}

void objectFree(object *obj) {
    assert(obj != NULL);
    vmDebugf("[free]\t\t%p\n", obj);
    switch (obj->type) {
    case OBJECT_TYPE_ARRAY:
        arrFree(obj->value.array);
        break;
    }
    xfree(obj);
}

const u32 MAX_STACK_SIZE = 1000;
const u32 GC_THRESHOLD = 1000;

typedef struct vm {
    object *heap_objects;
    object *stack[MAX_STACK_SIZE];
    u32 stack_size;
    u32 heap_max_objects;
    u32 heap_objects_cnt;
} vm;

void vmGC(vm *vm);

object *vmNewObject(vm *vm) {
    assert(vm != NULL);
    if (vm->heap_objects_cnt >= vm->heap_max_objects) vmGC(vm);

    object *obj = xmalloc(sizeof(*obj));
    vmDebugf("[alloc]\t\t%p\n", obj);
    obj->mark = false;
    obj->next = vm->heap_objects;
    vm->heap_objects = obj;
    vm->heap_objects_cnt++;
    return obj;
}

object *vmNewNumericObject(vm *vm, int value) {
    assert(vm != NULL);
    object *obj = vmNewObject(vm);
    obj->type = OBJECT_TYPE_NUMERIC;
    obj->value.numeric = value;
    return obj;
}

object *vmNewArrayObject(vm *vm) {
    assert(vm != NULL);
    object *obj = vmNewObject(vm);
    obj->type = OBJECT_TYPE_ARRAY;
    obj->value.array = NULL;
    return obj;
}

void vmPush(vm *vm, object *obj) {
    assert(vm != NULL);
    assert(vm->stack_size < MAX_STACK_SIZE);
    vmDebugf("[push]\t\t%p\n", obj);
    vm->stack[vm->stack_size++] = obj;
}

object *vmPop(vm *vm) {
    assert(vm != NULL);
    assert(vm->stack_size > 0);
    object *obj = vm->stack[--vm->stack_size];
    vmDebugf("[pop]\t\t%p\n", obj);
    return obj;
}

void vmPrint(vm *const vm) {
    assert(vm != NULL);
    printf("\n");
    printf("Root object:\t%p\n", vm->heap_objects);
    printf("Objects cnt:\t%d\n", vm->heap_objects_cnt);
    printf("Stack size:\t%d\n", vm->stack_size);
    printf("\n");
}

void vmGCMarkAll(vm *vm) {
    assert(vm != NULL);
    for (u32 i = 0; i < vm->stack_size; i++) {
        objectMark(vm->stack[i]);
    }
}

void vmGCSweep(vm *vm) {
    assert(vm != NULL);
    object **obj = &vm->heap_objects;
    while (*obj) {
        if ((*obj)->mark) {
            vmDebugf("[unmark]\t%p\n", *obj);
            (*obj)->mark = false;
            obj = &(*obj)->next;
        } else {
            object *tmp = (*obj)->next;
            objectFree(*obj);
            vm->heap_objects_cnt--;
            *obj = tmp;
        }
    }
}

void vmGC(vm *vm) {
    assert(vm != NULL);
    vmDebugf("[gc]\n");

    struct timespec before, after;
    clock_gettime(CLOCK_REALTIME, &before);

    vmGCMarkAll(vm);
    vmGCSweep(vm);

    clock_gettime(CLOCK_REALTIME, &after);

    totalGCCalls++;
    totalGCTime += (after.tv_sec - before.tv_sec) * 1000 + (after.tv_nsec - before.tv_nsec) / 1000000;

    vm->heap_max_objects = vm->heap_objects_cnt == 0 ? GC_THRESHOLD : vm->heap_objects_cnt * 2;
}

void play() {
    {
        printf("\nExample 1\n");
        printf("---------\n\n");

        vm vm = {
            .heap_objects = NULL,
            .stack = { 0 },
            .stack_size = 0,
            .heap_objects_cnt = 0,
            .heap_max_objects = GC_THRESHOLD,
        };

        vmPush(&vm, vmNewNumericObject(&vm, 11));
        vmPush(&vm, vmNewNumericObject(&vm, 22));
        
        vmPrint(&vm);
        vmGC(&vm);
        vmPrint(&vm);

        vmPop(&vm);
        vmPop(&vm);
        
        vmPrint(&vm);
        vmGC(&vm);
        vmPrint(&vm);
        vmGC(&vm);
    }

    {
        printf("\nExample 2\n");
        printf("---------\n\n");

        vm vm = {
            .heap_objects = NULL,
            .stack = { 0 },
            .stack_size = 0,
            .heap_objects_cnt = 0,
            .heap_max_objects = GC_THRESHOLD,
        };

        vmPush(&vm, vmNewNumericObject(&vm, 11));
        vmPush(&vm, vmNewNumericObject(&vm, 22));
        
        vmPrint(&vm);
        vmGC(&vm);
        vmPrint(&vm);

        object *obj = vmNewArrayObject(&vm);
        arrAppend(obj->value.array, vmPop(&vm));
        arrAppend(obj->value.array, vmPop(&vm));
        vmPush(&vm, obj);
        
        vmPrint(&vm);
        vmGC(&vm);
        vmPrint(&vm);
        vmGC(&vm);

        vmPop(&vm);
        vmPrint(&vm);
        vmGC(&vm);
        vmPrint(&vm);
    }
}

void bench() {
    printf("\nBenchmark\n");
    printf("---------\n");

    vm vm = {
        .heap_objects = NULL,
        .stack = { 0 },
        .stack_size = 0,
        .heap_objects_cnt = 0,
        .heap_max_objects = GC_THRESHOLD,
    };

    for (u32 i = 0; i < MAX_STACK_SIZE; i++) {
        for (u32 k = 0; k < i; k++) {
            object *obj = vmNewArrayObject(&vm);
            vmPush(&vm, obj);
            for (u32 j = 0; j < 1000; j++) {
                arrAppend(obj->value.array, vmNewNumericObject(&vm, j));
            }
        }

        for (u32 k = 0; k < i; k++) {
            vmPop(&vm);
        }

        printf(".");
        fflush(stdout);

        vmGC(&vm);
    }

    printf("\n\n");
    printf("total alloc:\t%lu\n", totalAlloc);
    printf("total dealloc:\t%lu\n", totalDealloc);
    printf("GC avg time:\t%f ms\n", totalGCTime / (f64)totalGCCalls);
    printf("GC calls:\t%zu\n", totalGCCalls);
    printf("\n");
}

i32 main(i32 argc, char **argv) {
    play();
    // bench();
    return 0;
}