diff options
| -rw-r--r-- | inc/gc.h | 84 | ||||
| -rw-r--r-- | inc/reducer.h | 3 | ||||
| -rw-r--r-- | src/gc.c | 650 | ||||
| -rw-r--r-- | src/main.c | 55 | ||||
| -rw-r--r-- | src/parse.c | 3 | ||||
| -rw-r--r-- | src/reducer.c | 87 | ||||
| -rw-r--r-- | src/store.c | 12 | ||||
| -rw-r--r-- | src/term.c | 9 |
8 files changed, 820 insertions, 83 deletions
diff --git a/inc/gc.h b/inc/gc.h new file mode 100644 index 0000000..0649559 --- /dev/null +++ b/inc/gc.h @@ -0,0 +1,84 @@ +/* + * gc - A simple mark and sweep garbage collector for C. + */ + +#ifndef __GC_H__ +#define __GC_H__ + +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> + +#define LOGLEVEL LOGLEVEL_DEBUG + +enum { + LOGLEVEL_CRITICAL, + LOGLEVEL_WARNING, + LOGLEVEL_INFO, + LOGLEVEL_DEBUG, + LOGLEVEL_NONE +}; + +extern const char *log_level_strings[]; + +#define log(level, fmt, ...) \ + do { \ + if (level <= LOGLEVEL) \ + fprintf(stderr, "[%s] %s:%s:%d: " fmt "\n", \ + log_level_strings[level], __func__, __FILE__, \ + __LINE__, __VA_ARGS__); \ + } while (0) + +#define LOG_CRITICAL(fmt, ...) log(LOGLEVEL_CRITICAL, fmt, __VA_ARGS__) +#define LOG_WARNING(fmt, ...) log(LOGLEVEL_WARNING, fmt, __VA_ARGS__) +#define LOG_INFO(fmt, ...) log(LOGLEVEL_INFO, fmt, __VA_ARGS__) +#define LOG_DEBUG(fmt, ...) log(LOGLEVEL_DEBUG, fmt, __VA_ARGS__) + +struct AllocationMap; + +typedef struct GarbageCollector { + struct AllocationMap *allocs; // allocation map + bool paused; // (temporarily) switch gc on/off + void *bos; // bottom of stack + size_t min_size; +} GarbageCollector; + +extern GarbageCollector gc; // Global garbage collector for all + // single-threaded applications + +/* + * Starting, stopping, pausing, resuming and running the GC. + */ +void gc_start(GarbageCollector *gc, void *bos); +void gc_start_ext(GarbageCollector *gc, void *bos, size_t initial_size, + size_t min_size, double downsize_load_factor, + double upsize_load_factor, double sweep_factor); +size_t gc_stop(GarbageCollector *gc); +void gc_pause(GarbageCollector *gc); +void gc_resume(GarbageCollector *gc); +size_t gc_run(GarbageCollector *gc); + +/* + * Allocating and deallocating memory. + */ +void *gc_malloc(GarbageCollector *gc, size_t size); +void *gc_malloc_static(GarbageCollector *gc, size_t size, void (*dtor)(void *)); +void *gc_malloc_ext(GarbageCollector *gc, size_t size, void (*dtor)(void *)); +void *gc_calloc(GarbageCollector *gc, size_t count, size_t size); +void *gc_calloc_ext(GarbageCollector *gc, size_t count, size_t size, + void (*dtor)(void *)); +void *gc_realloc(GarbageCollector *gc, void *ptr, size_t size); +void gc_free(GarbageCollector *gc, void *ptr); + +/* + * Lifecycle management + */ +void *gc_make_static(GarbageCollector *gc, void *ptr); + +/* + * Helper functions and stdlib replacements. + */ +char *gc_strdup(GarbageCollector *gc, const char *s); + +#endif /* !__GC_H__ */ diff --git a/inc/reducer.h b/inc/reducer.h index a5cfda1..82ea189 100644 --- a/inc/reducer.h +++ b/inc/reducer.h @@ -5,6 +5,7 @@ #include <term.h> -struct term *reduce(struct term *term, void (*callback)(int, char)); +struct term *reduce(struct term *term, void (*callback)(int, char, void *), + void *data); #endif diff --git a/src/gc.c b/src/gc.c new file mode 100644 index 0000000..688478e --- /dev/null +++ b/src/gc.c @@ -0,0 +1,650 @@ +#include <gc.h> + +#include <errno.h> +#include <setjmp.h> +#include <stdlib.h> +#include <string.h> +//#include "primes.h" + +const char *log_level_strings[] = { "CRIT", "WARN", "INFO", "DEBG", "NONE" }; + +/* + * Set log level for this compilation unit. If set to LOGLEVEL_DEBUG, + * the garbage collector will be very chatty. + */ +#undef LOGLEVEL +#define LOGLEVEL LOGLEVEL_INFO + +/* + * The size of a pointer. + */ +#define PTRSIZE sizeof(char *) + +/* + * Allocations can temporarily be tagged as "marked" an part of the + * mark-and-sweep implementation or can be tagged as "roots" which are + * not automatically garbage collected. The latter allows the implementation + * of global variables. + */ +#define GC_TAG_NONE 0x0 +#define GC_TAG_ROOT 0x1 +#define GC_TAG_MARK 0x2 + +/* + * Support for windows c compiler is added by adding this macro. + * Tested on: Microsoft (R) C/C++ Optimizing Compiler Version 19.24.28314 for x86 + */ +#if defined(_MSC_VER) +#define __builtin_frame_address(x) ((void)(x), _AddressOfReturnAddress()) +#endif + +/* + * Define a globally available GC object; this allows all code that + * includes the gc.h header to access a global static garbage collector. + * Convenient for single-threaded code, insufficient for multi-threaded + * use cases. Use the GC_NO_GLOBAL_GC flag to toggle. + */ +#ifndef GC_NO_GLOBAL_GC +GarbageCollector gc; // global GC object +#endif + +static bool is_prime(size_t n) +{ + /* https://stackoverflow.com/questions/1538644/c-determine-if-a-number-is-prime */ + if (n <= 3) + return n > 1; // as 2 and 3 are prime + else if (n % 2 == 0 || n % 3 == 0) + return false; // check if n is divisible by 2 or 3 + else { + for (size_t i = 5; i * i <= n; i += 6) { + if (n % i == 0 || n % (i + 2) == 0) + return false; + } + return true; + } +} + +static size_t next_prime(size_t n) +{ + while (!is_prime(n)) + ++n; + return n; +} + +/** + * The allocation object. + * + * The allocation object holds all metadata for a memory location + * in one place. + */ +typedef struct Allocation { + void *ptr; // mem pointer + size_t size; // allocated size in bytes + char tag; // the tag for mark-and-sweep + void (*dtor)(void *); // destructor + struct Allocation *next; // separate chaining +} Allocation; + +/** + * Create a new allocation object. + * + * Creates a new allocation object using the system `malloc`. + * + * @param[in] ptr The pointer to the memory to manage. + * @param[in] size The size of the memory range pointed to by `ptr`. + * @param[in] dtor A pointer to a destructor function that should be called + * before freeing the memory pointed to by `ptr`. + * @returns Pointer to the new allocation instance. + */ +static Allocation *gc_allocation_new(void *ptr, size_t size, + void (*dtor)(void *)) +{ + Allocation *a = (Allocation *)malloc(sizeof(Allocation)); + a->ptr = ptr; + a->size = size; + a->tag = GC_TAG_NONE; + a->dtor = dtor; + a->next = NULL; + return a; +} + +/** + * Delete an allocation object. + * + * Deletes the allocation object pointed to by `a`, but does *not* + * free the memory pointed to by `a->ptr`. + * + * @param a The allocation object to delete. + */ +static void gc_allocation_delete(Allocation *a) +{ + free(a); +} + +/** + * The allocation hash map. + * + * The core data structure is a hash map that holds the allocation + * objects and allows O(1) retrieval given the memory location. Collision + * resolution is implemented using separate chaining. + */ +typedef struct AllocationMap { + size_t capacity; + size_t min_capacity; + double downsize_factor; + double upsize_factor; + double sweep_factor; + size_t sweep_limit; + size_t size; + Allocation **allocs; +} AllocationMap; + +/** + * Determine the current load factor of an `AllocationMap`. + * + * Calculates the load factor of the hash map as the quotient of the size and + * the capacity of the hash map. + * + * @param am The allocationo map to calculate the load factor for. + * @returns The load factor of the allocation map `am`. + */ +static double gc_allocation_map_load_factor(AllocationMap *am) +{ + return (double)am->size / (double)am->capacity; +} + +static AllocationMap * +gc_allocation_map_new(size_t min_capacity, size_t capacity, double sweep_factor, + double downsize_factor, double upsize_factor) +{ + AllocationMap *am = (AllocationMap *)malloc(sizeof(AllocationMap)); + am->min_capacity = next_prime(min_capacity); + am->capacity = next_prime(capacity); + if (am->capacity < am->min_capacity) + am->capacity = am->min_capacity; + am->sweep_factor = sweep_factor; + am->sweep_limit = (int)(sweep_factor * am->capacity); + am->downsize_factor = downsize_factor; + am->upsize_factor = upsize_factor; + am->allocs = (Allocation **)calloc(am->capacity, sizeof(Allocation *)); + am->size = 0; + LOG_DEBUG("Created allocation map (cap=%ld, siz=%ld)", am->capacity, + am->size); + return am; +} + +static void gc_allocation_map_delete(AllocationMap *am) +{ + // Iterate over the map + LOG_DEBUG("Deleting allocation map (cap=%ld, siz=%ld)", am->capacity, + am->size); + Allocation *alloc, *tmp; + for (size_t i = 0; i < am->capacity; ++i) { + if ((alloc = am->allocs[i])) { + // Make sure to follow the chain inside a bucket + while (alloc) { + tmp = alloc; + alloc = alloc->next; + // free the management structure + gc_allocation_delete(tmp); + } + } + } + free(am->allocs); + free(am); +} + +static size_t gc_hash(void *ptr) +{ + return ((uintptr_t)ptr) >> 3; +} + +static void gc_allocation_map_resize(AllocationMap *am, size_t new_capacity) +{ + if (new_capacity <= am->min_capacity) { + return; + } + // Replaces the existing items array in the hash table + // with a resized one and pushes items into the new, correct buckets + LOG_DEBUG("Resizing allocation map (cap=%ld, siz=%ld) -> (cap=%ld)", + am->capacity, am->size, new_capacity); + Allocation **resized_allocs = + calloc(new_capacity, sizeof(Allocation *)); + + for (size_t i = 0; i < am->capacity; ++i) { + Allocation *alloc = am->allocs[i]; + while (alloc) { + Allocation *next_alloc = alloc->next; + size_t new_index = gc_hash(alloc->ptr) % new_capacity; + alloc->next = resized_allocs[new_index]; + resized_allocs[new_index] = alloc; + alloc = next_alloc; + } + } + free(am->allocs); + am->capacity = new_capacity; + am->allocs = resized_allocs; + am->sweep_limit = + am->size + am->sweep_factor * (am->capacity - am->size); +} + +static bool gc_allocation_map_resize_to_fit(AllocationMap *am) +{ + double load_factor = gc_allocation_map_load_factor(am); + if (load_factor > am->upsize_factor) { + LOG_DEBUG("Load factor %0.3g > %0.3g. Triggering upsize.", + load_factor, am->upsize_factor); + gc_allocation_map_resize(am, next_prime(am->capacity * 2)); + return true; + } + if (load_factor < am->downsize_factor) { + LOG_DEBUG("Load factor %0.3g < %0.3g. Triggering downsize.", + load_factor, am->downsize_factor); + gc_allocation_map_resize(am, next_prime(am->capacity / 2)); + return true; + } + return false; +} + +static Allocation *gc_allocation_map_get(AllocationMap *am, void *ptr) +{ + size_t index = gc_hash(ptr) % am->capacity; + Allocation *cur = am->allocs[index]; + while (cur) { + if (cur->ptr == ptr) { + return cur; + } + cur = cur->next; + } + return NULL; +} + +static Allocation *gc_allocation_map_put(AllocationMap *am, void *ptr, + size_t size, void (*dtor)(void *)) +{ + size_t index = gc_hash(ptr) % am->capacity; + LOG_DEBUG("PUT request for allocation ix=%ld", index); + Allocation *alloc = gc_allocation_new(ptr, size, dtor); + Allocation *cur = am->allocs[index]; + Allocation *prev = NULL; + /* Upsert if ptr is already known (e.g. dtor update). */ + while (cur != NULL) { + if (cur->ptr == ptr) { + // found it + alloc->next = cur->next; + if (!prev) { + // position 0 + am->allocs[index] = alloc; + } else { + // in the list + prev->next = alloc; + } + gc_allocation_delete(cur); + LOG_DEBUG("AllocationMap Upsert at ix=%ld", index); + return alloc; + } + prev = cur; + cur = cur->next; + } + /* Insert at the front of the separate chaining list */ + cur = am->allocs[index]; + alloc->next = cur; + am->allocs[index] = alloc; + am->size++; + LOG_DEBUG("AllocationMap insert at ix=%ld", index); + void *p = alloc->ptr; + if (gc_allocation_map_resize_to_fit(am)) { + alloc = gc_allocation_map_get(am, p); + } + return alloc; +} + +static void gc_allocation_map_remove(AllocationMap *am, void *ptr, + bool allow_resize) +{ + // ignores unknown keys + size_t index = gc_hash(ptr) % am->capacity; + Allocation *cur = am->allocs[index]; + Allocation *prev = NULL; + Allocation *next; + while (cur != NULL) { + next = cur->next; + if (cur->ptr == ptr) { + // found it + if (!prev) { + // first item in list + am->allocs[index] = cur->next; + } else { + // not the first item in the list + prev->next = cur->next; + } + gc_allocation_delete(cur); + am->size--; + } else { + // move on + prev = cur; + } + cur = next; + } + if (allow_resize) { + gc_allocation_map_resize_to_fit(am); + } +} + +static void *gc_mcalloc(size_t count, size_t size) +{ + if (!count) + return malloc(size); + return calloc(count, size); +} + +static bool gc_needs_sweep(GarbageCollector *gc) +{ + return gc->allocs->size > gc->allocs->sweep_limit; +} + +static void *gc_allocate(GarbageCollector *gc, size_t count, size_t size, + void (*dtor)(void *)) +{ + /* Allocation logic that generalizes over malloc/calloc. */ + + /* Check if we reached the high-water mark and need to clean up */ + if (gc_needs_sweep(gc) && !gc->paused) { + size_t freed_mem = gc_run(gc); + LOG_DEBUG("Garbage collection cleaned up %lu bytes.", + freed_mem); + } + /* With cleanup out of the way, attempt to allocate memory */ + void *ptr = gc_mcalloc(count, size); + size_t alloc_size = count ? count * size : size; + /* If allocation fails, force an out-of-policy run to free some memory and try again. */ + if (!ptr && !gc->paused && (errno == EAGAIN || errno == ENOMEM)) { + gc_run(gc); + ptr = gc_mcalloc(count, size); + } + /* Start managing the memory we received from the system */ + if (ptr) { + LOG_DEBUG("Allocated %zu bytes at %p", alloc_size, (void *)ptr); + Allocation *alloc = gc_allocation_map_put(gc->allocs, ptr, + alloc_size, dtor); + /* Deal with metadata allocation failure */ + if (alloc) { + LOG_DEBUG("Managing %zu bytes at %p", alloc_size, + (void *)alloc->ptr); + ptr = alloc->ptr; + } else { + /* We failed to allocate the metadata, fail cleanly. */ + free(ptr); + ptr = NULL; + } + } + return ptr; +} + +static void gc_make_root(GarbageCollector *gc, void *ptr) +{ + Allocation *alloc = gc_allocation_map_get(gc->allocs, ptr); + if (alloc) { + alloc->tag |= GC_TAG_ROOT; + } +} + +void *gc_malloc(GarbageCollector *gc, size_t size) +{ + return gc_malloc_ext(gc, size, NULL); +} + +void *gc_malloc_static(GarbageCollector *gc, size_t size, void (*dtor)(void *)) +{ + void *ptr = gc_malloc_ext(gc, size, dtor); + gc_make_root(gc, ptr); + return ptr; +} + +void *gc_make_static(GarbageCollector *gc, void *ptr) +{ + gc_make_root(gc, ptr); + return ptr; +} + +void *gc_malloc_ext(GarbageCollector *gc, size_t size, void (*dtor)(void *)) +{ + return gc_allocate(gc, 0, size, dtor); +} + +void *gc_calloc(GarbageCollector *gc, size_t count, size_t size) +{ + return gc_calloc_ext(gc, count, size, NULL); +} + +void *gc_calloc_ext(GarbageCollector *gc, size_t count, size_t size, + void (*dtor)(void *)) +{ + return gc_allocate(gc, count, size, dtor); +} + +void *gc_realloc(GarbageCollector *gc, void *p, size_t size) +{ + Allocation *alloc = gc_allocation_map_get(gc->allocs, p); + if (p && !alloc) { + // the user passed an unknown pointer + errno = EINVAL; + return NULL; + } + void *q = realloc(p, size); + if (!q) { + // realloc failed but p is still valid + return NULL; + } + if (!p) { + // allocation, not reallocation + Allocation *alloc = + gc_allocation_map_put(gc->allocs, q, size, NULL); + return alloc->ptr; + } + if (p == q) { + // successful reallocation w/o copy + alloc->size = size; + } else { + // successful reallocation w/ copy + void (*dtor)(void *) = alloc->dtor; + gc_allocation_map_remove(gc->allocs, p, true); + gc_allocation_map_put(gc->allocs, q, size, dtor); + } + return q; +} + +void gc_free(GarbageCollector *gc, void *ptr) +{ + Allocation *alloc = gc_allocation_map_get(gc->allocs, ptr); + if (alloc) { + if (alloc->dtor) { + alloc->dtor(ptr); + } + free(ptr); + gc_allocation_map_remove(gc->allocs, ptr, true); + } else { + LOG_WARNING("Ignoring request to free unknown pointer %p", + (void *)ptr); + } +} + +void gc_start(GarbageCollector *gc, void *bos) +{ + gc_start_ext(gc, bos, 1024, 1024, 0.2, 0.8, 0.5); +} + +void gc_start_ext(GarbageCollector *gc, void *bos, size_t initial_capacity, + size_t min_capacity, double downsize_load_factor, + double upsize_load_factor, double sweep_factor) +{ + double downsize_limit = + downsize_load_factor > 0.0 ? downsize_load_factor : 0.2; + double upsize_limit = + upsize_load_factor > 0.0 ? upsize_load_factor : 0.8; + sweep_factor = sweep_factor > 0.0 ? sweep_factor : 0.5; + gc->paused = false; + gc->bos = bos; + initial_capacity = initial_capacity < min_capacity ? min_capacity : + initial_capacity; + gc->allocs = gc_allocation_map_new(min_capacity, initial_capacity, + sweep_factor, downsize_limit, + upsize_limit); + LOG_DEBUG("Created new garbage collector (cap=%ld, siz=%ld).", + gc->allocs->capacity, gc->allocs->size); +} + +void gc_pause(GarbageCollector *gc) +{ + gc->paused = true; +} + +void gc_resume(GarbageCollector *gc) +{ + gc->paused = false; +} + +void gc_mark_alloc(GarbageCollector *gc, void *ptr) +{ + Allocation *alloc = gc_allocation_map_get(gc->allocs, ptr); + /* Mark if alloc exists and is not tagged already, otherwise skip */ + if (alloc && !(alloc->tag & GC_TAG_MARK)) { + LOG_DEBUG("Marking allocation (ptr=%p)", ptr); + alloc->tag |= GC_TAG_MARK; + /* Iterate over allocation contents and mark them as well */ + LOG_DEBUG("Checking allocation (ptr=%p, size=%lu) contents", + ptr, alloc->size); + for (char *p = (char *)alloc->ptr; + p <= (char *)alloc->ptr + alloc->size - PTRSIZE; ++p) { + LOG_DEBUG( + "Checking allocation (ptr=%p) @%lu with value %p", + ptr, p - ((char *)alloc->ptr), *(void **)p); + gc_mark_alloc(gc, *(void **)p); + } + } +} + +void gc_mark_stack(GarbageCollector *gc) +{ + LOG_DEBUG("Marking the stack (gc@%p) in increments of %ld", (void *)gc, + sizeof(char)); + void *tos = __builtin_frame_address(0); + void *bos = gc->bos; + /* The stack grows towards smaller memory addresses, hence we scan tos->bos. + * Stop scanning once the distance between tos & bos is too small to hold a valid pointer */ + for (char *p = (char *)tos; p <= (char *)bos - PTRSIZE; ++p) { + gc_mark_alloc(gc, *(void **)p); + } +} + +void gc_mark_roots(GarbageCollector *gc) +{ + LOG_DEBUG("Marking roots%s", ""); + for (size_t i = 0; i < gc->allocs->capacity; ++i) { + Allocation *chunk = gc->allocs->allocs[i]; + while (chunk) { + if (chunk->tag & GC_TAG_ROOT) { + LOG_DEBUG("Marking root @ %p", chunk->ptr); + gc_mark_alloc(gc, chunk->ptr); + } + chunk = chunk->next; + } + } +} + +void gc_mark(GarbageCollector *gc) +{ + /* Note: We only look at the stack and the heap, and ignore BSS. */ + LOG_DEBUG("Initiating GC mark (gc@%p)", (void *)gc); + /* Scan the heap for roots */ + gc_mark_roots(gc); + /* Dump registers onto stack and scan the stack */ + void (*volatile _mark_stack)(GarbageCollector *) = gc_mark_stack; + jmp_buf ctx; + memset(&ctx, 0, sizeof(jmp_buf)); + setjmp(ctx); + _mark_stack(gc); +} + +size_t gc_sweep(GarbageCollector *gc) +{ + LOG_DEBUG("Initiating GC sweep (gc@%p)", (void *)gc); + size_t total = 0; + for (size_t i = 0; i < gc->allocs->capacity; ++i) { + Allocation *chunk = gc->allocs->allocs[i]; + Allocation *next = NULL; + /* Iterate over separate chaining */ + while (chunk) { + if (chunk->tag & GC_TAG_MARK) { + LOG_DEBUG("Found used allocation %p (ptr=%p)", + (void *)chunk, (void *)chunk->ptr); + /* unmark */ + chunk->tag &= ~GC_TAG_MARK; + chunk = chunk->next; + } else { + LOG_DEBUG( + "Found unused allocation %p (%lu bytes @ ptr=%p)", + (void *)chunk, chunk->size, + (void *)chunk->ptr); + /* no reference to this chunk, hence delete it */ + total += chunk->size; + if (chunk->dtor) { + chunk->dtor(chunk->ptr); + } + free(chunk->ptr); + /* and remove it from the bookkeeping */ + next = chunk->next; + gc_allocation_map_remove(gc->allocs, chunk->ptr, + false); + chunk = next; + } + } + } + gc_allocation_map_resize_to_fit(gc->allocs); + return total; +} + +/** + * Unset the ROOT tag on all roots on the heap. + * + * @param gc A pointer to a garbage collector instance. + */ +void gc_unroot_roots(GarbageCollector *gc) +{ + LOG_DEBUG("Unmarking roots%s", ""); + for (size_t i = 0; i < gc->allocs->capacity; ++i) { + Allocation *chunk = gc->allocs->allocs[i]; + while (chunk) { + if (chunk->tag & GC_TAG_ROOT) { + chunk->tag &= ~GC_TAG_ROOT; + } + chunk = chunk->next; + } + } +} + +size_t gc_stop(GarbageCollector *gc) +{ + gc_unroot_roots(gc); + size_t collected = gc_sweep(gc); + gc_allocation_map_delete(gc->allocs); + return collected; +} + +size_t gc_run(GarbageCollector *gc) +{ + LOG_DEBUG("Initiating GC run (gc@%p)", (void *)gc); + gc_mark(gc); + return gc_sweep(gc); +} + +char *gc_strdup(GarbageCollector *gc, const char *s) +{ + size_t len = strlen(s) + 1; + void *new = gc_malloc(gc, len); + + if (new == NULL) { + return NULL; + } + return (char *)memcpy(new, s, len); +} @@ -5,9 +5,10 @@ #include <parse.h> #include <term.h> #include <reducer.h> +#include <gc.h> #ifndef TEST -static void callback(int i, char ch) +static void callback(int i, char ch, void *data) { printf("%d: %c\n", i, ch); } @@ -44,6 +45,17 @@ int main(void) #include <errno.h> #include <time.h> +struct test { + struct term *in; + struct term *res; + struct term *red; + char *trans; + struct { + int alpha; + int trans; + } equivalency; +}; + static char *read_file(const char *path) { FILE *f = fopen(path, "rb"); @@ -70,30 +82,23 @@ static char *read_file(const char *path) return string; } -// global vars suck I know but how could I do it any other way? -static struct { - struct term *in; - struct term *res; - struct term *red; - char *trans; - struct { - int alpha; - int trans; - } equivalency; -} tests[NTESTS] = { 0 }; -static int current = 0; - -static void callback(int i, char ch) +static void callback(int i, char ch, void *data) { - if (ch != tests[current].trans[i]) { + struct test *test = data; + if (ch != test->trans[i]) { fprintf(stderr, "Transition deviation at index %d!\n", i); - tests[current].equivalency.trans = 0; + test->equivalency.trans = 0; } - fprintf(stderr, "\n%d: %c\n", i, ch); + /* fprintf(stderr, "\n%d: %c\n", i, ch); */ } -int main(void) +int main(int argc, char **argv) { + gc_start(&gc, &argc); + (void)argv; + + struct test tests[NTESTS] = { 0 }; + char in_template[] = TESTDIR "x.in"; char red_template[] = TESTDIR "x.red"; char trans_template[] = TESTDIR "x.trans"; @@ -118,14 +123,18 @@ int main(void) } clock_t begin = clock(); - for (current = 0; current < NTESTS; current++) { - tests[current].res = reduce(tests[current].in, callback); - printf("Test %d done\n", current + 1 + STARTTEST); + for (int i = 0; i < NTESTS; i++) { + tests[i].res = reduce(tests[i].in, callback, &tests[i]); + printf("Test %d done\n", i + 1 + STARTTEST); } clock_t end = clock(); for (int i = 0; i < NTESTS; i++) { to_bruijn(tests[i].res); + print_term(tests[i].res); + printf("\n"); + print_term(tests[i].red); + printf("\n"); tests[i].equivalency.alpha = alpha_equivalency(tests[i].res, tests[i].red); free_term(tests[i].res); @@ -142,5 +151,7 @@ int main(void) i + 1 + STARTTEST, tests[i].equivalency.alpha, tests[i].equivalency.trans); } + + gc_stop(&gc); } #endif diff --git a/src/parse.c b/src/parse.c index 33ca556..9408bde 100644 --- a/src/parse.c +++ b/src/parse.c @@ -5,6 +5,7 @@ #include <stdio.h> #include <parse.h> +#include <gc.h> #include <term.h> static struct term *rec(const char **term) @@ -35,7 +36,7 @@ static struct term *rec(const char **term) struct term *parse(const char *term) { - struct term *parsed = rec(&term); + struct term *parsed = gc_make_static(&gc, rec(&term)); to_barendregt(parsed); return parsed; } diff --git a/src/reducer.c b/src/reducer.c index 1d4f5e6..1372a50 100644 --- a/src/reducer.c +++ b/src/reducer.c @@ -10,6 +10,7 @@ #include <murmur3.h> #include <store.h> #include <term.h> +#include <gc.h> struct tracked { void *stuff; @@ -59,7 +60,7 @@ static int name_generator(void) static struct stack *stack_push(struct stack *stack, void *data) { - struct stack *new = malloc(sizeof(*new)); + struct stack *new = gc_malloc(&gc, sizeof(*new)); new->data = data; new->next = stack; return new; @@ -90,9 +91,7 @@ static void cconf(struct conf *conf, struct stack *stack, struct term *term) static int transition_1(struct term **term, struct store **store, struct stack **stack) { - struct term *orig = *term; - - struct closure *closure = malloc(sizeof(*closure)); + struct closure *closure = gc_malloc(&gc, sizeof(*closure)); closure->term = (*term)->u.app.rhs; closure->store = *store; @@ -111,15 +110,15 @@ static int transition_1(struct term **term, struct store **store, static int transition_2(struct stack **stack, struct term **term, struct store *store) { - struct box *box = malloc(sizeof(*box)); + struct box *box = gc_malloc(&gc, sizeof(*box)); box->state = TODO; box->term = 0; - struct closure *closure = malloc(sizeof(*closure)); + struct closure *closure = gc_malloc(&gc, sizeof(*closure)); closure->term = *term; closure->store = store; - struct cache *cache = malloc(sizeof(*cache)); + struct cache *cache = gc_malloc(&gc, sizeof(*cache)); cache->box = box; cache->term = new_term(CLOSURE); cache->term->u.other = closure; @@ -134,11 +133,9 @@ static int transition_2(struct stack **stack, struct term **term, static int transition_3(struct term **term, struct store **store, struct stack **stack, struct box *box) { - struct term *orig_term = *term; - struct store *orig_store = *store; assert(box->term->type == CLOSURE); - struct cache *cache = malloc(sizeof(*cache)); + struct cache *cache = gc_malloc(&gc, sizeof(*cache)); cache->box = box; cache->term = new_term(VAR); @@ -154,9 +151,8 @@ static int transition_3(struct term **term, struct store **store, } static int transition_4(struct stack **stack, struct term **term, - struct store *store, struct box *box) + struct box *box) { - struct term *orig = *term; *stack = *stack; *term = box->term; @@ -169,7 +165,6 @@ static int transition_5(struct stack **stack, struct term **term, struct cache *cache = peek_term->u.other; struct box *box = cache->box; - struct term **orig = &box->term; box->state = DONE; box->term = *term; @@ -183,9 +178,7 @@ static int transition_6(struct term **term, struct store **store, struct stack **stack, struct term *peek_term, struct closure *closure) { - struct term *orig = *term; - - struct box *box = malloc(sizeof(*box)); + struct box *box = gc_malloc(&gc, sizeof(*box)); box->state = TODO; box->term = peek_term->u.app.rhs; @@ -200,15 +193,14 @@ static int transition_7(struct term **term, struct store **store, struct stack **stack, struct box *box, struct closure *closure) { - struct term *orig = *term; int x = name_generator(); - struct box *var_box = malloc(sizeof(*var_box)); + struct box *var_box = gc_malloc(&gc, sizeof(*var_box)); var_box->state = DONE; var_box->term = new_term(VAR); var_box->term->u.var.name = x; - struct cache *cache = malloc(sizeof(*cache)); + struct cache *cache = gc_malloc(&gc, sizeof(*cache)); cache->box = box; cache->term = new_term(VAR); @@ -231,8 +223,6 @@ static int transition_7(struct term **term, struct store **store, static int transition_8(struct stack **stack, struct term **term, struct box *box) { - struct term *orig = *term; - *stack = *stack; *term = box->term; @@ -242,8 +232,6 @@ static int transition_8(struct stack **stack, struct term **term, static int transition_9(struct term **term, struct store **store, struct stack **stack, struct term *peek_term) { - struct term *orig = *term; - struct closure *closure = peek_term->u.app.rhs->u.other; struct term *app = new_term(APP); @@ -260,8 +248,6 @@ static int transition_9(struct term **term, struct store **store, static int transition_10(struct stack **stack, struct term **term, struct term *peek_term) { - struct term *orig = *term; - struct term *app = new_term(APP); app->u.app.lhs = peek_term->u.app.lhs; app->u.app.rhs = *term; @@ -275,8 +261,6 @@ static int transition_10(struct stack **stack, struct term **term, static int transition_11(struct stack **stack, struct term **term, struct term *peek_term) { - struct term *orig = *term; - struct term *abs = new_term(ABS); abs->u.abs.name = peek_term->u.abs.name; abs->u.abs.term = *term; @@ -288,7 +272,7 @@ static int transition_11(struct stack **stack, struct term **term, } static int transition_closure(struct conf *conf, int i, - void (*callback)(int, char)) + void (*callback)(int, char, void *), void *data) { struct term *term = conf->u.econf.term; struct store *store = conf->u.econf.store; @@ -297,31 +281,30 @@ static int transition_closure(struct conf *conf, int i, int ret = 1; switch (term->type) { case APP: // (1) - callback(i, '1'); + callback(i, '1', data); ret = transition_1(&term, &store, &stack); econf(conf, term, store, stack); return ret; case ABS: // (2) - callback(i, '2'); + callback(i, '2', data); ret = transition_2(&stack, &term, store); cconf(conf, stack, term); return ret; case VAR:; struct box *box = store_get(store, &term->u.var.name, 0); - int unbound = 0; if (!box) { - box = malloc(sizeof(*box)); + box = gc_malloc(&gc, sizeof(*box)); box->state = DONE; box->term = term; } if (box->state == TODO) { // (3) - callback(i, '3'); + callback(i, '3', data); ret = transition_3(&term, &store, &stack, box); econf(conf, term, store, stack); return ret; } else if (box->state == DONE) { // (4) - callback(i, '4'); - ret = transition_4(&stack, &term, store, box); + callback(i, '4', data); + ret = transition_4(&stack, &term, box); cconf(conf, stack, term); return ret; } @@ -334,7 +317,7 @@ static int transition_closure(struct conf *conf, int i, } static int transition_computed(struct conf *conf, int i, - void (*callback)(int, char)) + void (*callback)(int, char, void *), void *data) { struct stack *stack = conf->u.cconf.stack; struct term *term = conf->u.cconf.term; @@ -348,7 +331,7 @@ static int transition_computed(struct conf *conf, int i, struct cache *cache = peek_term->u.other; struct term *cache_term = cache->term; if (cache_term->type == VAR && !cache_term->u.var.name) { - callback(i, '5'); + callback(i, '5', data); ret = transition_5(&stack, &term, peek_term); cconf(conf, stack, term); return ret; @@ -361,7 +344,7 @@ static int transition_computed(struct conf *conf, int i, struct closure *closure = ((struct cache *)term->u.other)->term->u.other; if (closure->term->type == ABS) { - callback(i, '6'); + callback(i, '6', data); struct store *store; ret = transition_6(&term, &store, &stack, peek_term, closure); @@ -376,14 +359,14 @@ static int transition_computed(struct conf *conf, int i, ((struct cache *)term->u.other)->term->u.other; if (closure->term->type == ABS && box->state == TODO && !box->term) { // (7) - callback(i, '7'); + callback(i, '7', data); struct store *store; ret = transition_7(&term, &store, &stack, box, closure); econf(conf, term, store, stack); return ret; } if (closure->term->type == ABS && box->state == DONE) { // (8) - callback(i, '8'); + callback(i, '8', data); ret = transition_8(&stack, &term, box); cconf(conf, stack, term); return ret; @@ -393,7 +376,7 @@ static int transition_computed(struct conf *conf, int i, peek_term->u.app.lhs->type == VAR && !peek_term->u.app.lhs->u.var.name && peek_term->u.app.rhs->type == CLOSURE) { // (9) - callback(i, '9'); + callback(i, '9', data); struct store *store; ret = transition_9(&term, &store, &stack, peek_term); econf(conf, term, store, stack); @@ -402,7 +385,7 @@ static int transition_computed(struct conf *conf, int i, if (peek_term && peek_term->type == APP && peek_term->u.app.rhs->type == VAR && !peek_term->u.app.rhs->u.var.name) { // (10) - callback(i, 'A'); + callback(i, 'A', data); ret = transition_10(&stack, &term, peek_term); cconf(conf, stack, term); return ret; @@ -410,7 +393,7 @@ static int transition_computed(struct conf *conf, int i, if (peek_term && peek_term->type == ABS && peek_term->u.abs.term->type == VAR && !peek_term->u.abs.term->u.var.name) { // (11) - callback(i, 'B'); + callback(i, 'B', data); ret = transition_11(&stack, &term, peek_term); cconf(conf, stack, term); return ret; @@ -423,23 +406,25 @@ static int transition_computed(struct conf *conf, int i, return 1; } -static int transition(struct conf *conf, int i, void (*callback)(int, char)) +static int transition(struct conf *conf, int i, + void (*callback)(int, char, void *), void *data) { if (conf->type == ECONF) { - return transition_closure(conf, i, callback); + return transition_closure(conf, i, callback, data); } else if (conf->type == CCONF) { - return transition_computed(conf, i, callback); + return transition_computed(conf, i, callback, data); } fprintf(stderr, "Invalid transition state %x\n", conf->type); return 1; } static struct conf *for_each_state(struct conf *conf, int i, - void (*callback)(int, char)) + void (*callback)(int, char, void *), + void *data) { int ret = 0; while (!ret) - ret = transition(conf, i++, callback); + ret = transition(conf, i++, callback, data); return conf; } @@ -454,7 +439,8 @@ static uint32_t hash_var(void *key) return murmur3_32((uint8_t *)key, sizeof(int), 0); } -struct term *reduce(struct term *term, void (*callback)(int, char)) +struct term *reduce(struct term *term, void (*callback)(int, char, void *), + void *data) { struct stack stack = { 0 }; struct store *store = store_new(hash_var, hash_var_equal); @@ -464,9 +450,10 @@ struct term *reduce(struct term *term, void (*callback)(int, char)) .u.econf.store = store, .u.econf.stack = &stack, }; - for_each_state(&conf, 0, callback); + for_each_state(&conf, 0, callback, data); assert(conf.type == CCONF); struct term *ret = duplicate_term(conf.u.cconf.term); + return ret; } diff --git a/src/store.c b/src/store.c index ae1d1bd..7bab153 100644 --- a/src/store.c +++ b/src/store.c @@ -35,6 +35,7 @@ #include <string.h> #include <store.h> +#include <gc.h> #define store_node_debug_fmt \ "node{element_arity=%u, element_map=%08x, branch_arity=%u, branch_map=%08x, ref_count=%u}" @@ -249,7 +250,7 @@ static void node_destroy(struct node *node) DEBUG_NOTICE(" destroying " store_node_debug_fmt "@%p\n", store_node_debug_args(node), (void *)node); - free(node); + gc_free(&gc, node); } // reference counting @@ -283,7 +284,7 @@ static struct node *node_new(uint32_t element_map, uint32_t branch_map, { const size_t content_size = STORE_NODE_ELEMENTS_SIZE(element_arity) + STORE_NODE_BRANCHES_SIZE(branch_arity); - struct node *result = malloc(sizeof(*result) + content_size); + struct node *result = gc_malloc(&gc, sizeof(*result) + content_size); result->element_arity = element_arity; result->branch_arity = branch_arity; @@ -432,7 +433,8 @@ static struct collision_node * collision_node_new(const STORE_NODE_ELEMENT_T *values, uint8_t element_arity) { size_t content_size = sizeof(STORE_NODE_ELEMENT_T) * element_arity; - struct collision_node *result = malloc(sizeof(*result) + content_size); + struct collision_node *result = + gc_malloc(&gc, sizeof(*result) + content_size); result->element_arity = element_arity; result->branch_arity = 0; @@ -868,7 +870,7 @@ static int node_equals(struct node *left, struct node *right, static struct store *store_from(struct node *root, unsigned length, STORE_HASHFN_T(hash), STORE_EQUALSFN_T(equals)) { - struct store *result = malloc(sizeof(*result)); + struct store *result = gc_malloc(&gc, sizeof(*result)); result->ref_count = 0; result->root = root; result->length = length; @@ -882,7 +884,7 @@ void store_destroy(struct store **store) DEBUG_NOTICE("destroying store@%p\n", (void *)*store); store_node_release((*store)->root); - free(*store); + gc_free(&gc, *store); *store = NULL; } @@ -5,6 +5,7 @@ #include <stdio.h> #include <term.h> +#include <gc.h> static int name_generator(void) { @@ -93,7 +94,7 @@ void to_bruijn(struct term *term) struct term *new_term(term_type type) { - struct term *term = calloc(1, sizeof(*term)); + struct term *term = gc_calloc(&gc, 1, sizeof(*term)); if (!term) { fprintf(stderr, "Out of memory!\n"); abort(); @@ -154,15 +155,15 @@ void free_term(struct term *term) switch (term->type) { case ABS: free_term(term->u.abs.term); - free(term); + gc_free(&gc, term); break; case APP: free_term(term->u.app.lhs); free_term(term->u.app.rhs); - free(term); + gc_free(&gc, term); break; case VAR: - free(term); + gc_free(&gc, term); break; default: fprintf(stderr, "Invalid type %d\n", term->type); |