Toy GC

gcmalloc.c

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

typedef struct {
    void      *gcp_ptr;
    int        gcp_mark;
    int        gcp_size;
    int        gcp_need_scan;
} gc_ptr_t;

typedef struct {
    void      *gc_start;
    gc_ptr_t   gc_ptrs[256];
    int        gc_ptrs_index;
} gc_t;

void gc_init(gc_t *gc, void *start_ptr);
void *gc_malloc(gc_t *gc, int size, int need_scan);
void gc_scan_region(gc_t *gc, void *start, int size);
void gc_mark_ptr(gc_t *gc, void *ptr);
void gc_sweep(gc_t *gc);
void gc_collect(gc_t *gc);

void
gc_init(gc_t *gc, void *start_ptr)
{
    printf("start_ptr = %p\n", start_ptr);

    memset(gc, 0, sizeof(*gc));
    gc->gc_start = start_ptr;
}

void *
gc_malloc(gc_t *gc, int size, int need_scan)
{
    void *p;

    if ((p = malloc(size)) != NULL) {
        printf("malloc: %p\n", p);

        gc->gc_ptrs[gc->gc_ptrs_index].gcp_ptr = p;
        gc->gc_ptrs[gc->gc_ptrs_index].gcp_size = size;
        gc->gc_ptrs[gc->gc_ptrs_index].gcp_need_scan = need_scan;
        gc->gc_ptrs_index++;
    }

    return p;
}

void
gc_scan_region(gc_t *gc, void *start, int size)
{
    int i;
    uint8_t *p;

    printf("scan: ptr %p size %d\n", start, size);

    for (p = (uint8_t *) start; p <= (uint8_t *) start + size - sizeof(void *); p++)
        gc_mark_ptr(gc, *((void **) p));
}

void
gc_mark_ptr(gc_t *gc, void *ptr)
{
    int i;

    for (i = 0; i < gc->gc_ptrs_index; i++) {
        if (gc->gc_ptrs[i].gcp_ptr == ptr) {
            if (gc->gc_ptrs[i].gcp_mark == 0) {
                printf("mark %p\n", ptr);
                gc->gc_ptrs[i].gcp_mark = 1;

                if (gc->gc_ptrs[i].gcp_need_scan)
                    gc_scan_region(gc, ptr, gc->gc_ptrs[i].gcp_size);
            }
        }
    }
}

void
gc_sweep(gc_t *gc)
{
    int i;

    for (i = 0; i < gc->gc_ptrs_index; i++) {
        if (gc->gc_ptrs[i].gcp_mark == 0) {
            printf("free %p\n", gc->gc_ptrs[i].gcp_ptr);
            free(gc->gc_ptrs[i].gcp_ptr);
        }
    }
}

void
gc_collect(gc_t *gc)
{
    gc_scan_region(gc, &gc, (uint8_t *) gc->gc_start - (uint8_t *) &gc);
    gc_sweep(gc);
}


struct test {
    void *ptr;
};

int
main(int argc, char *argv[])
{
    gc_t gc;
    struct test *t;

    gc_init(&gc, &gc);
    t = (struct test *) gc_malloc(&gc, 10, 1);
    t->ptr = gc_malloc(&gc, 10, 0);

    t = NULL;
    gc_collect(&gc);

    return 0;
}