gc.c

#ifdef DO_DEBUG
#define DEBUG(exp) (exp)
#else
#define DEBUG(exp)
#endif

#ifndef DO_DEBUG
#define NDEBUG
#endif

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <errno.h>
#include <assert.h>
#include <unistd.h>
#include <setjmp.h>
#include "gc.h"

/* ========================================================================== */
/*  mini_gc_malloc                                                            */
/* ========================================================================== */

typedef struct header {
    size_t flags;
    size_t size;
    struct header *next_free;
} Header;

typedef struct gc_heap {
    Header *slot;
    size_t size;
} GC_Heap;

#define TINY_HEAP_SIZE 0x4000
#define PTRSIZE ((size_t) sizeof(void *))
#define HEADER_SIZE ((size_t) sizeof(Header))
#define HEAP_LIMIT 10000
#define ALIGN(x,a) (((x) + (a - 1)) & ~(a - 1))
#define NEXT_HEADER(x) ((Header *)((size_t)(x+1) + x->size))

/* flags */
#define FL_ALLOC 0x1
#define FL_MARK 0x2
#define FL_SET(x, f) (((Header *)x)->flags |= f)
#define FL_UNSET(x, f) (((Header *)x)->flags &= ~(f))
#define FL_TEST(x, f) (((Header *)x)->flags & f)

static Header *free_list;
static GC_Heap gc_heaps[HEAP_LIMIT];
static size_t gc_heaps_used = 0;


static Header *
add_heap(size_t req_size)
{
    void *p;
    Header *align_p;

    if (gc_heaps_used >= HEAP_LIMIT) {
        fputs("OutOfMemory Error", stderr);
        abort();
    }

    if (req_size < TINY_HEAP_SIZE)
        req_size = TINY_HEAP_SIZE;

    if((p = sbrk(req_size + PTRSIZE + HEADER_SIZE)) == (void *)-1)
        return NULL;

    /* address alignment */
    align_p = gc_heaps[gc_heaps_used].slot = (Header *)ALIGN((size_t)p, PTRSIZE);
    req_size = gc_heaps[gc_heaps_used].size = req_size;
    align_p->size = req_size;
    align_p->next_free = align_p;
    gc_heaps_used++;

    return align_p;
}

static Header *
grow(size_t req_size)
{
    Header *cp, *up;

    if (!(cp = add_heap(req_size)))
        return NULL;

    up = (Header *) cp;
    mini_gc_free((void *)(up+1));
    return free_list;
}

void *
mini_gc_malloc(size_t req_size)
{
    Header *p, *prevp;
    size_t do_gc = 0;

    req_size = ALIGN(req_size, PTRSIZE);

    if (req_size <= 0) {
        return NULL;
    }
    if ((prevp = free_list) == NULL) {
        if (!(p = add_heap(TINY_HEAP_SIZE))) {
            return NULL;
        }
        prevp = free_list = p;
    }
    for (p = prevp->next_free; ; prevp = p, p = p->next_free) {
        if (p->size >= req_size) {
            if (p->size == req_size)
                /* just fit */
                prevp->next_free = p->next_free;
            else {
                /* too big */
                p->size -= (req_size + HEADER_SIZE);
                p = NEXT_HEADER(p);
                p->size = req_size;
            }
            free_list = prevp;
            FL_SET(p, FL_ALLOC);
            return (void *)(p+1);
        }
        if (p == free_list) {
            if (!do_gc) {
                garbage_collect();
                do_gc = 1;
            }
            else if ((p = grow(req_size)) == NULL)
                return NULL;
        }
    }
}

void
mini_gc_free(void *ptr)
{
    Header *target, *hit;

    target = (Header *)ptr - 1;

    /* search join point of target to free_list */
    for (hit = free_list; !(target > hit && target < hit->next_free); hit = hit->next_free)
        /* heap end? And hit(search)? */
        if (hit >= hit->next_free &&
            (target > hit || target < hit->next_free))
            break;

    if (NEXT_HEADER(target) == hit->next_free) {
        /* merge */
        target->size += (hit->next_free->size + HEADER_SIZE);
        target->next_free = hit->next_free->next_free;
    }
    else {
        /* join next free block */
        target->next_free = hit->next_free;
    }
    if (NEXT_HEADER(hit) == target) {
        /* merge */
        hit->size += (target->size + HEADER_SIZE);
        hit->next_free = target->next_free;
    }
    else {
        /* join before free block */
        hit->next_free = target;
    }
    free_list = hit;
    target->flags = 0;
}




/* ========================================================================== */
/*  mini_gc                                                                   */
/* ========================================================================== */

struct root_range {
    void * start;
    void * end;
};

#define IS_MARKED(x) (FL_TEST(x, FL_ALLOC) && FL_TEST(x, FL_MARK))
#define ROOT_RANGES_LIMIT 1000

static struct root_range root_ranges[ROOT_RANGES_LIMIT];
static size_t root_ranges_used = 0;
static void * stack_start = NULL;
static void * stack_end = NULL;
static GC_Heap *hit_cache = NULL;

static GC_Heap *
is_pointer_to_heap(void *ptr)
{
    size_t i;

    if (hit_cache &&
        ((void *)hit_cache->slot) <= ptr &&
        (size_t)ptr < (((size_t)hit_cache->slot) + hit_cache->size))
        return hit_cache;

    for (i = 0; i < gc_heaps_used;  i++) {
        if ((((void *)gc_heaps[i].slot) <= ptr) &&
            ((size_t)ptr < (((size_t)gc_heaps[i].slot) + gc_heaps[i].size))) {
            hit_cache = &gc_heaps[i];
            return &gc_heaps[i];
        }
    }
    return NULL;
}

static Header *
get_header(GC_Heap *gh, void *ptr)
{
    Header *p, *pend, *pnext;

    pend = (Header *)(((size_t)gh->slot) + gh->size);
    for (p = gh->slot; p < pend; p = pnext) {
        pnext = NEXT_HEADER(p);
        if ((void *)(p+1) <= ptr && ptr < (void *)pnext) {
            return p;
        }
    }
    return NULL;
}

void
gc_init(void)
{
    long dummy;

    /* referenced bdw-gc mark_rts.c */
    dummy = 42;

    /* check stack grow */
    stack_start = ((void *)&dummy);
}

static void
set_stack_end(void)
{
    void *tmp;
    long dummy;

    /* referenced bdw-gc mark_rts.c */
    dummy = 42;

    stack_end = (void *)&dummy;
}

static void gc_mark_range(void *start, void *end);

static void
gc_mark(void * ptr)
{
    GC_Heap *gh;
    Header *hdr;

    /* mark check */
    if (!(gh = is_pointer_to_heap(ptr))) return;
    if (!(hdr = get_header(gh, ptr))) return;
    if (!FL_TEST(hdr, FL_ALLOC)) return;
    if (FL_TEST(hdr, FL_MARK)) return;

    /* marking */
    FL_SET(hdr, FL_MARK);
    DEBUG(printf("mark ptr : %p, header : %p\n", ptr, hdr));

    /* mark children */
    gc_mark_range((void *)(hdr+1), (void *)NEXT_HEADER(hdr));
}

static void
gc_mark_range(void *start, void *end)
{
    void *p;

    for (p = start; p < end; p++) {
        gc_mark(*(void **)p);
    }
}

static void
gc_mark_register(void)
{
    jmp_buf env;
    size_t i;
    
    setjmp(env);
    for (i = 0; i < sizeof(env); i++) {
        gc_mark(((void **)env)[i]);
    }
}

static void
gc_mark_stack(void)
{
    set_stack_end();
    if (stack_start > stack_end) {
        gc_mark_range(stack_end, stack_start);
    }
    else {
        gc_mark_range(stack_start, stack_end);
    }
}

static void
gc_sweep(void)
{
    size_t i;
    Header *p, *pend, *pnext;

    for (i = 0; i < gc_heaps_used; i++) {
        pend = (Header *)(((size_t)gc_heaps[i].slot) + gc_heaps[i].size);
        for (p = gc_heaps[i].slot; p < pend; p = NEXT_HEADER(p)) {
            if (FL_TEST(p, FL_ALLOC)) {
                if (FL_TEST(p, FL_MARK)) {
                    DEBUG(printf("mark unset : %p\n", p));
                    FL_UNSET(p, FL_MARK);
                }
                else {
                    mini_gc_free(p+1);
                }
            }
        }
    }
}

void
add_roots(void * start, void * end)
{
    void *tmp;
    if (start > end) {
        tmp = start;
        start = end;
        end = tmp;
    }
    root_ranges[root_ranges_used].start = start;
    root_ranges[root_ranges_used].end = end;
    root_ranges_used++;

    if (root_ranges_used >= ROOT_RANGES_LIMIT) {
        fputs("Root OverFlow", stderr);
        abort();
    }
}

void
garbage_collect(void)
{
    size_t i;

    /* marking machine context */
    gc_mark_register();
    gc_mark_stack();

    /* marking roots */
    for (i = 0; i < root_ranges_used; i++) {
        gc_mark_range(root_ranges[i].start, root_ranges[i].end);
    }

    /* sweeping */
    gc_sweep();
}


/* ========================================================================== */
/*  test                                                                      */
/* ========================================================================== */

static void
test_mini_gc_malloc_free(void)
{
    void *p1, *p2, *p3;

    /* malloc check */
    p1 = (void *)mini_gc_malloc(10);
    p2 = (void *)mini_gc_malloc(10);
    p3 = (void *)mini_gc_malloc(10);
    assert(((Header *)p1-1)->size == ALIGN(10, PTRSIZE));
    assert(((Header *)p1-1)->flags == FL_ALLOC);
    assert((Header *)(((size_t)(free_list+1)) + free_list->size) == ((Header *)p3-1));

    /* free check */
    mini_gc_free(p1);
    mini_gc_free(p3);
    mini_gc_free(p2);
    assert(free_list->next_free == free_list);
    assert((void *)gc_heaps[0].slot == (void *)free_list);
    assert(gc_heaps[0].size == TINY_HEAP_SIZE);
    assert(((Header *)p1-1)->flags == 0);

    /* grow check */
    p1 = mini_gc_malloc(TINY_HEAP_SIZE+80);
    assert(gc_heaps_used == 2);
    assert(gc_heaps[1].size == (TINY_HEAP_SIZE+80));
    mini_gc_free(p1);
}

static void
test_garbage_collect(void) {
    void *p;
    p = mini_gc_malloc(100);
    assert(FL_TEST((((Header *)p)-1), FL_ALLOC));
    p = 0;
    garbage_collect();
}

static void
test_garbage_collect_load_test(void) {
    void *p;
    int i;
    for (i = 0; i < 2000; i++) {
        p = mini_gc_malloc(100);
    }
    assert((((Header *)p)-1)->flags);
    assert(stack_end != stack_start);
}

static void
test(void)
{
    gc_init();
    test_mini_gc_malloc_free();
    test_garbage_collect();
    test_garbage_collect_load_test();
}


int
main(int argc, char **argv)
{
    if (argc == 2 && strcmp(argv[1], "test") == 0)  test();
    return 0;
}