diff options
| -rw-r--r-- | .gitmodules | 3 | ||||
| -rw-r--r-- | inc/gc.h | 84 | ||||
| m--------- | lib/bdwgc | 0 | ||||
| -rw-r--r-- | makefile | 4 | ||||
| -rw-r--r-- | readme.md | 16 | ||||
| -rw-r--r-- | src/gc.c | 650 | ||||
| -rw-r--r-- | src/main.c | 10 | ||||
| -rw-r--r-- | src/parse.c | 3 | ||||
| -rw-r--r-- | src/reducer.c | 20 | ||||
| -rw-r--r-- | src/store.c | 10 | ||||
| -rw-r--r-- | src/term.c | 8 |
11 files changed, 30 insertions, 778 deletions
diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..7050620 --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "lib/bdwgc"] + path = lib/bdwgc + url = https://github.com/ivmai/bdwgc diff --git a/inc/gc.h b/inc/gc.h deleted file mode 100644 index 0649559..0000000 --- a/inc/gc.h +++ /dev/null @@ -1,84 +0,0 @@ -/* - * 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/lib/bdwgc b/lib/bdwgc new file mode 160000 +Subproject 1c2f2c679927538fa4969f85c67fafc3b1dddb2 @@ -2,18 +2,18 @@ # SPDX-License-Identifier: MIT CC = gcc -LD = ld TG = ctags BUILD = $(PWD)/build SRC = $(PWD)/src INC = $(PWD)/inc +LIB = $(PWD)/lib SRCS = $(wildcard $(SRC)/*.c) OBJS = $(patsubst $(SRC)/%.c, $(BUILD)/%.o, $(SRCS)) CFLAGS_DEBUG = -Wno-error -g -O0 -Wno-unused -fsanitize=address,undefined,leak CFLAGS_WARNINGS = -Wall -Wextra -Wshadow -Wpointer-arith -Wwrite-strings -Wredundant-decls -Wnested-externs -Wmissing-declarations -Wstrict-prototypes -Wmissing-prototypes -Wcast-qual -Wswitch-default -Wswitch-enum -Wunreachable-code -Wundef -Wold-style-definition -pedantic -Wno-switch-enum -CFLAGS = $(CFLAGS_WARNINGS) -std=c99 -fno-omit-frame-pointer -Ofast -I$(INC) -ggdb3 +CFLAGS = $(CFLAGS_WARNINGS) -std=c99 -Ofast -L$(LIB)/bdwgc/lib -lgc -I$(LIB)/bdwgc/inc -I$(INC) ifdef TEST # TODO: Somehow clean automagically CFLAGS += -DTEST -DNTESTS=$(TEST) @@ -11,26 +11,16 @@ of functional programming languages - Based on bleeding-edge research results - Exponentially big normal forms of the family $e_n=λx.c_nωx$, where - $ω:=λx.xx$ and $c_n$ denotes the $n$th Church numeral, consume only + $ω:=λx.xx$ and $c_n$ denotes the $n$-th Church numeral, consume only a linear in $n$ amount of memory and are computed in linear time\[0\] -## Why C? - -You might realize that the reduction transitions are of a very -functional nature and aren't that obvious to implement in non-functional -languages. - -I used C because **(1)** most functional languages use automatic memory -management (often using periodic garbage collecting) which unnecessarily -slows down the transitions, **(2)** there aren't that many efficient -lambda calculus reducers in C out there, **(3)** it's a fun challenge -and **(4)** I like C. - ## Libraries - [CHAMP](https://github.com/ammut/immutable-c-ollections) \[MIT\]: Underrated efficient hash array mapped trie +- [BDWGC](https://github.com/ivmai/bdwgc) \[MIT\]: Boehm-Demers-Weiser + Garbage Collector ## Research diff --git a/src/gc.c b/src/gc.c deleted file mode 100644 index 688478e..0000000 --- a/src/gc.c +++ /dev/null @@ -1,650 +0,0 @@ -#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); -} @@ -94,8 +94,7 @@ static void callback(int i, char ch, void *data) int main(int argc, char **argv) { - gc_start(&gc, &argc); - (void)argv; + GC_INIT(); struct test tests[NTESTS] = { 0 }; @@ -131,14 +130,11 @@ int main(int argc, char **argv) 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); free_term(tests[i].red); + free(tests[i].trans); } printf("=== SUMMARY ===\n"); @@ -151,7 +147,5 @@ int main(int argc, char **argv) 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 9408bde..33ca556 100644 --- a/src/parse.c +++ b/src/parse.c @@ -5,7 +5,6 @@ #include <stdio.h> #include <parse.h> -#include <gc.h> #include <term.h> static struct term *rec(const char **term) @@ -36,7 +35,7 @@ static struct term *rec(const char **term) struct term *parse(const char *term) { - struct term *parsed = gc_make_static(&gc, rec(&term)); + struct term *parsed = rec(&term); to_barendregt(parsed); return parsed; } diff --git a/src/reducer.c b/src/reducer.c index 1372a50..754a433 100644 --- a/src/reducer.c +++ b/src/reducer.c @@ -60,7 +60,7 @@ static int name_generator(void) static struct stack *stack_push(struct stack *stack, void *data) { - struct stack *new = gc_malloc(&gc, sizeof(*new)); + struct stack *new = GC_malloc(sizeof(*new)); new->data = data; new->next = stack; return new; @@ -91,7 +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 closure *closure = gc_malloc(&gc, sizeof(*closure)); + struct closure *closure = GC_malloc(sizeof(*closure)); closure->term = (*term)->u.app.rhs; closure->store = *store; @@ -110,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 = gc_malloc(&gc, sizeof(*box)); + struct box *box = GC_malloc(sizeof(*box)); box->state = TODO; box->term = 0; - struct closure *closure = gc_malloc(&gc, sizeof(*closure)); + struct closure *closure = GC_malloc(sizeof(*closure)); closure->term = *term; closure->store = store; - struct cache *cache = gc_malloc(&gc, sizeof(*cache)); + struct cache *cache = GC_malloc(sizeof(*cache)); cache->box = box; cache->term = new_term(CLOSURE); cache->term->u.other = closure; @@ -135,7 +135,7 @@ static int transition_3(struct term **term, struct store **store, { assert(box->term->type == CLOSURE); - struct cache *cache = gc_malloc(&gc, sizeof(*cache)); + struct cache *cache = GC_malloc(sizeof(*cache)); cache->box = box; cache->term = new_term(VAR); @@ -178,7 +178,7 @@ static int transition_6(struct term **term, struct store **store, struct stack **stack, struct term *peek_term, struct closure *closure) { - struct box *box = gc_malloc(&gc, sizeof(*box)); + struct box *box = GC_malloc(sizeof(*box)); box->state = TODO; box->term = peek_term->u.app.rhs; @@ -195,12 +195,12 @@ static int transition_7(struct term **term, struct store **store, { int x = name_generator(); - struct box *var_box = gc_malloc(&gc, sizeof(*var_box)); + struct box *var_box = GC_malloc(sizeof(*var_box)); var_box->state = DONE; var_box->term = new_term(VAR); var_box->term->u.var.name = x; - struct cache *cache = gc_malloc(&gc, sizeof(*cache)); + struct cache *cache = GC_malloc(sizeof(*cache)); cache->box = box; cache->term = new_term(VAR); @@ -293,7 +293,7 @@ static int transition_closure(struct conf *conf, int i, case VAR:; struct box *box = store_get(store, &term->u.var.name, 0); if (!box) { - box = gc_malloc(&gc, sizeof(*box)); + box = GC_malloc(sizeof(*box)); box->state = DONE; box->term = term; } diff --git a/src/store.c b/src/store.c index 7bab153..116b59e 100644 --- a/src/store.c +++ b/src/store.c @@ -250,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); - gc_free(&gc, node); + GC_free(node); } // reference counting @@ -284,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 = gc_malloc(&gc, sizeof(*result) + content_size); + struct node *result = GC_malloc(sizeof(*result) + content_size); result->element_arity = element_arity; result->branch_arity = branch_arity; @@ -434,7 +434,7 @@ 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 = - gc_malloc(&gc, sizeof(*result) + content_size); + GC_malloc(sizeof(*result) + content_size); result->element_arity = element_arity; result->branch_arity = 0; @@ -870,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 = gc_malloc(&gc, sizeof(*result)); + struct store *result = GC_malloc(sizeof(*result)); result->ref_count = 0; result->root = root; result->length = length; @@ -884,7 +884,7 @@ void store_destroy(struct store **store) DEBUG_NOTICE("destroying store@%p\n", (void *)*store); store_node_release((*store)->root); - gc_free(&gc, *store); + GC_free(*store); *store = NULL; } @@ -94,7 +94,7 @@ void to_bruijn(struct term *term) struct term *new_term(term_type type) { - struct term *term = gc_calloc(&gc, 1, sizeof(*term)); + struct term *term = GC_malloc(sizeof(*term)); if (!term) { fprintf(stderr, "Out of memory!\n"); abort(); @@ -155,15 +155,15 @@ void free_term(struct term *term) switch (term->type) { case ABS: free_term(term->u.abs.term); - gc_free(&gc, term); + GC_free(term); break; case APP: free_term(term->u.app.lhs); free_term(term->u.app.rhs); - gc_free(&gc, term); + GC_free(term); break; case VAR: - gc_free(&gc, term); + GC_free(term); break; default: fprintf(stderr, "Invalid type %d\n", term->type); |