From 335d4ca1276199be242a32a21c353e647ee942e9 Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Fri, 9 Oct 2015 22:38:33 -0400 Subject: [PATCH] added garbage collector --- source/libparse/ast.c | 2 +- source/libparse/gc.c | 310 +++++++++++++++++++++++++++++++++++++ source/libparse/grammar.c | 91 ++++++----- source/libparse/lexer.c | 7 +- source/libparse/libparse.h | 28 +++- source/libparse/parser.c | 16 +- source/sclpl/main.c | 3 +- 7 files changed, 392 insertions(+), 65 deletions(-) create mode 100644 source/libparse/gc.c diff --git a/source/libparse/ast.c b/source/libparse/ast.c index b27eb3f..947fcf2 100644 --- a/source/libparse/ast.c +++ b/source/libparse/ast.c @@ -108,7 +108,7 @@ void block_append(AST* expr) size_t block_size(AST* block) { (void)block; - return NULL; + return 0; } AST* block_get(size_t index) diff --git a/source/libparse/gc.c b/source/libparse/gc.c new file mode 100644 index 0000000..abd90a1 --- /dev/null +++ b/source/libparse/gc.c @@ -0,0 +1,310 @@ +#include + +typedef struct obj_t { + uintptr_t refs; + destructor_t destructor; +} obj_t; + +typedef struct hash_entry_t { + obj_t* object; + unsigned int hash; + struct hash_entry_t* next; +} hash_entry_t; + +typedef struct { + size_t size; + size_t bkt_count; + hash_entry_t** buckets; +} hash_t; + +static void hash_set(hash_t* hash, hash_entry_t* entry); + +/*****************************************************************************/ + +#define NUM_PRIMES (sizeof(Primes)/sizeof(unsigned int)) + +static unsigned int Primes[] = { + 5, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, + 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, + 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, + 805306457, 1610612741 +}; + +static unsigned int num_buckets(unsigned int idx) { + assert(idx < NUM_PRIMES); + return Primes[idx]; +} + +static void hash_init(hash_t* hash) +{ + hash->size = 0; + hash->bkt_count = 0; + hash->buckets = (hash_entry_t**)calloc(sizeof(hash_entry_t*), num_buckets(hash->bkt_count)); +} + +static void find_entry(hash_entry_t** parent, hash_entry_t** current, hash_entry_t* entry) +{ + while(*current != NULL) { + if (((*current)->hash == entry->hash) && + ((*current)->object == entry->object)) + break; + *parent = *current; + *current = (*current)->next; + } +} + +static void rehash(hash_t* hash) +{ + unsigned int oldcount, i; + hash_entry_t** oldbuckets; + hash_entry_t *node, *entry; + if ((hash->bkt_count+1) < NUM_PRIMES) { + oldcount = hash->bkt_count++; + oldbuckets = hash->buckets; + hash->buckets = (hash_entry_t**)calloc(sizeof(hash_entry_t*), num_buckets(hash->bkt_count)); + hash->size = 0; + /* Iterate over all of the old buckets */ + for (i = 0; i < num_buckets(oldcount); i++) { + node = oldbuckets[i]; + /* re-insert all entries in the bucket into the new bucket table */ + while (node != NULL) { + entry = node; + node = entry->next; + hash_set(hash, entry); + } + } + /* Free the old bucket table */ + free(oldbuckets); + } +} + +static uint64_t hash64(uint64_t key) +{ + key = (~key) + (key << 21); + key = key ^ (key >> 24); + key = (key + (key << 3)) + (key << 8); + key = key ^ (key >> 14); + key = (key + (key << 2)) + (key << 4); + key = key ^ (key >> 28); + key = key + (key << 31); + return key; +} + +static size_t hash_size(hash_t* hash) +{ + return hash->size; +} + +static void hash_set(hash_t* hash, hash_entry_t* entry) +{ + unsigned int index; + hash_entry_t *parent, *node, *deadite; + if (hash->size >= num_buckets(hash->bkt_count)) + rehash(hash); + entry->hash = hash64((uint64_t)(entry->object)); + index = (entry->hash % num_buckets(hash->bkt_count)); + parent = NULL; + node = hash->buckets[index]; + deadite = NULL; + find_entry(&parent, &node, entry); + if ((parent == NULL) && (node == NULL)) { + hash->buckets[index] = entry; + entry->next = NULL; + hash->size++; + } else if (node == NULL) { + parent->next = entry; + entry->next = NULL; + hash->size++; + } else if (parent == NULL) { + deadite = node; + entry->next = deadite->next; + hash->buckets[index] = entry; + } else { + deadite = node; + entry->next = deadite->next; + parent->next = entry; + } + if (deadite != NULL) + free(deadite); +} + +static hash_entry_t* hash_del(hash_t* hash, hash_entry_t* entry) +{ + unsigned int index; + hash_entry_t *parent, *node, *ret = NULL; + entry->hash = hash64((uint64_t)(entry->object)); + index = (entry->hash % num_buckets(hash->bkt_count)); + parent = NULL; + node = hash->buckets[index]; + find_entry(&parent, &node, entry); + if (node != NULL) { + ret = node; + node = node->next; + if (parent != NULL) + parent->next = node; + else + hash->buckets[index] = node; + hash->size--; + } + return ret; +} + +/*****************************************************************************/ + +static void** Stack_Bottom; +static hash_t Zero_Count_Table; +static hash_t Multi_Ref_Table; +static hash_t Working_Table; + +static void gc_mark_region(void** start, void** end) { + hash_entry_t lookup = {0, 0, 0}; + hash_entry_t* entry; + for (; start <= end; start++) { + lookup.object = *start; + entry = hash_del(&Working_Table, &lookup); + if (entry != NULL) { + hash_set(&Zero_Count_Table, entry); + } + } +} + +static void gc_mark_stack(void) { + void* stack_top = NULL; + /* Determine which way the stack grows and scan it for pointers */ + if (&stack_top < Stack_Bottom) { + gc_mark_region(&stack_top, Stack_Bottom); + } else { + gc_mark_region(Stack_Bottom, &stack_top); + } +} + +static void gc_mark(void) { + jmp_buf env; + volatile int noinline = 1; + /* Flush Registers to Stack */ + if (noinline) { + memset(&env, 0x55, sizeof(jmp_buf)); + (void)setjmp(env); + } + /* Avoid Inlining function call so that we scan the registers along with + * the stack */ + (noinline ? gc_mark_stack : NULL)(); +} + +static void gc_sweep(void) { + unsigned int i; + /* Delete all the entries in the hash */ + for (i = 0; i < num_buckets(Working_Table.bkt_count); i++) { + hash_entry_t* node = Working_Table.buckets[i]; + Working_Table.buckets[i] = NULL; + while (node != NULL) { + hash_entry_t* deadite = node; + obj_t* obj = ((obj_t*)(deadite->object)-1); + if (obj->destructor != NULL) + obj->destructor(deadite->object); + free(deadite); + node = node->next; + } + } + free(Working_Table.buckets); +} + +void gc_init(void** stack_bottom) +{ + Stack_Bottom = stack_bottom; + hash_init(&Zero_Count_Table); + hash_init(&Multi_Ref_Table); +} + +void gc_deinit(void) +{ +} + +void gc_collect(void) { + Working_Table = Zero_Count_Table; + hash_init(&Zero_Count_Table); + gc_mark(); + gc_sweep(); +} + +void* gc_alloc(size_t size, destructor_t destructor) +{ + hash_entry_t* entry = (hash_entry_t*)malloc(sizeof(hash_entry_t) + sizeof(obj_t) + size); + obj_t* p_obj = (obj_t*)(entry+1); + void* p_data = (void*)(p_obj+1); + entry->object = p_data; + p_obj->refs = 0; + p_obj->destructor = destructor; + hash_set(&Zero_Count_Table, entry); + if (hash_size(&Zero_Count_Table) >= 500) + gc_collect(); + return p_data; +} + +void* gc_addref(void* ptr) +{ + hash_entry_t lookup = {0, 0, 0}; + hash_entry_t* entry; + obj_t* obj = ((obj_t*)ptr-1); + obj->refs++; + if (obj->refs == 1) { + lookup.object = obj; + entry = hash_del(&Zero_Count_Table, &lookup); + assert(entry != NULL); + hash_set(&Multi_Ref_Table, entry); + } + return ptr; +} + +void gc_delref(void* ptr) +{ + hash_entry_t lookup = {0, 0, 0}; + hash_entry_t* entry; + obj_t* obj = ((obj_t*)ptr-1); + obj->refs--; + if (obj->refs == 0) { + lookup.object = obj; + entry = hash_del(&Multi_Ref_Table, &lookup); + assert(entry != NULL); + hash_set(&Zero_Count_Table, entry); + } +} + +void gc_swapref(void** dest, void* newref) +{ + void* oldref = *dest; + *dest = gc_addref(newref); + gc_delref(oldref); +} + +/*****************************************************************************/ + +int main(int argc, char** argv) +{ + void* stack_bottom = NULL; + gc_init(&stack_bottom); + atexit(gc_deinit); + return user_main(argc, argv); +} + +///int user_main(int argc, char** argv) { +/// uint8_t* foo; +/// (void)argc; +/// (void)argv; +/// foo = (uint8_t*)gc_alloc(42,NULL); +/// printf("refs: %lu\n", hash_size(&Zero_Count_Table)); +/// gc_collect(); +/// *foo = 42; +/// printf("data: %d\n", (int)*foo); +/// (void)foo; +/// printf("refs: %lu\n", hash_size(&Zero_Count_Table)); +/// printf("ref: %p\n", foo); +/// foo = NULL; +/// gc_collect(); +/// printf("refs: %lu\n", hash_size(&Zero_Count_Table)); +/// printf("ref: %p\n", foo); +/// gc_collect(); +/// printf("refs: %lu\n", hash_size(&Zero_Count_Table)); +/// return 0; +///} + diff --git a/source/libparse/grammar.c b/source/libparse/grammar.c index 5b48b0f..96e3537 100644 --- a/source/libparse/grammar.c +++ b/source/libparse/grammar.c @@ -6,66 +6,62 @@ */ #include -static void require(Parser* p); -static void type_annotation(Parser* p); -static void type_definition(Parser* p); -static void type(Parser* p); -static void tuple(Parser* p); -static void function(Parser* p); -static void definition(Parser* p); -static void expression(Parser* p); -static void literal(Parser* p); -static void arglist(Parser* p); -static void if_stmnt(Parser* p); -static void fn_stmnt(Parser* p); +static AST* require(Parser* p); +static AST* type_annotation(Parser* p); +static AST* type_definition(Parser* p); +static AST* type(Parser* p); +static AST* tuple(Parser* p); +static AST* function(Parser* p); +static AST* definition(Parser* p); +static AST* expression(Parser* p); +static AST* literal(Parser* p); +static AST* arglist(Parser* p); +static AST* if_stmnt(Parser* p); +static AST* fn_stmnt(Parser* p); AST* toplevel(Parser* p) { - AST* tree = NULL; - try { - if (accept_str(p, T_ID, "require")) - require(p); - else if (accept_str(p, T_ID, "type")) - type_definition(p); - else if (accept_str(p, T_ID, "ann")) - type_annotation(p); - else if (accept_str(p, T_ID, "def")) - definition(p); - else - expression(p); - //tree = get_tree(p); - } catch(ParseException) { - /* Do nothing, the tree is bad */ - } - return tree; + if (accept_str(p, T_ID, "require")) + return require(p); + else if (accept_str(p, T_ID, "type")) + return type_definition(p); + else if (accept_str(p, T_ID, "ann")) + return type_annotation(p); + else if (accept_str(p, T_ID, "def")) + return definition(p); + else + return expression(p); } -static void require(Parser* p) +static AST* require(Parser* p) { - shifttok(p, T_STRING); + //shifttok(p, T_STRING); expect(p, T_END); //reduce(Require); + return NULL; } -static void type_annotation(Parser* p) +static AST* type_annotation(Parser* p) { - shifttok(p, T_ID); + //shifttok(p, T_ID); type(p); expect(p, T_END); //reduce(Annotation); + return NULL; } /*****************************************************************************/ -static void type_definition(Parser* p) +static AST* type_definition(Parser* p) { expect(p, T_ID); expect_str(p, T_ID, "is"); type(p); expect(p, T_END); + return NULL; } -static void type(Parser* p) { +static AST* type(Parser* p) { if (accept(p, T_LBRACE)) { tuple(p); } else { @@ -74,9 +70,10 @@ static void type(Parser* p) { function(p); } } + return NULL; } -static void tuple(Parser* p) { +static AST* tuple(Parser* p) { //size_t mrk = mark(p); //insert(p, T_ID, lexer_dup("tuple")); do { @@ -84,9 +81,10 @@ static void tuple(Parser* p) { } while (accept(p, T_COMMA)); expect(p, T_RBRACE); //reduce(p, mrk); + return NULL; } -static void function(Parser* p) { +static AST* function(Parser* p) { //size_t mark1 = mark(p) - 1; //size_t mark2 = mark(p); while (!accept(p, T_RPAR)) { @@ -96,9 +94,10 @@ static void function(Parser* p) { } //reduce(p, mark2); //reduce(p, mark1); + return NULL; } -static void definition(Parser* p) +static AST* definition(Parser* p) { //size_t mrk = mark(p); expect(p,T_ID); @@ -110,9 +109,10 @@ static void definition(Parser* p) expect(p,T_END); } //reduce(p, mrk); + return NULL; } -static void expression(Parser* p) +static AST* expression(Parser* p) { if (accept(p, T_LPAR)) { //size_t mrk = mark(p); @@ -131,9 +131,10 @@ static void expression(Parser* p) } else { literal(p); } + return NULL; } -static void literal(Parser* p) +static AST* literal(Parser* p) { switch (peek(p)->type) { case T_BOOL: @@ -147,9 +148,10 @@ static void literal(Parser* p) default: error(p, "Expected a literal"); } + return NULL; } -static void arglist(Parser* p) +static AST* arglist(Parser* p) { //size_t mrk = mark(p); expect(p, T_LPAR); @@ -160,9 +162,10 @@ static void arglist(Parser* p) } expect(p, T_RPAR); //reduce(p, mrk); + return NULL; } -static void if_stmnt(Parser* p) +static AST* if_stmnt(Parser* p) { //size_t mrk = mark(p); expression(p); @@ -172,9 +175,10 @@ static void if_stmnt(Parser* p) } expect(p,T_END); //reduce(p, mrk); + return NULL; } -static void fn_stmnt(Parser* p) +static AST* fn_stmnt(Parser* p) { //size_t mark1 = mark(p); expect(p, T_LPAR); @@ -191,5 +195,6 @@ static void fn_stmnt(Parser* p) } expect(p, T_END); //reduce(p, mark1); + return NULL; } diff --git a/source/libparse/lexer.c b/source/libparse/lexer.c index 1392e28..1952084 100644 --- a/source/libparse/lexer.c +++ b/source/libparse/lexer.c @@ -8,7 +8,7 @@ static char* dupstring(const char* old) { size_t length = strlen(old); - char* str = (char*)mem_allocate(length+1, NULL); + char* str = (char*)gc_alloc(length+1, NULL); memcpy(str, old, length); str[length] = '\0'; return str; @@ -24,12 +24,12 @@ static void token_free(void* obj) (tok->type != T_INT) && (tok->type != T_FLOAT) && (NULL != tok->value.text)) - mem_release(tok->value.text); + gc_delref(tok->value.text); } static Tok* Token(TokType type) { - Tok* tok = (Tok*)mem_allocate(sizeof(Tok), &token_free); + Tok* tok = (Tok*)gc_alloc(sizeof(Tok), &token_free); tok->type = type; return tok; } @@ -342,6 +342,7 @@ static Tok* boolean(char* text) static Tok* classify(const char* file, size_t line, size_t col, char* text) { Tok* tok = NULL; + (void)file; if (0 == strcmp(text,"end")) { tok = Token(T_END); } else if (char_oneof("()[]{};,'", text[0])) { diff --git a/source/libparse/libparse.h b/source/libparse/libparse.h index 83f69fe..7113321 100644 --- a/source/libparse/libparse.h +++ b/source/libparse/libparse.h @@ -1,9 +1,6 @@ /** @file libparse.h - @brief TODO: Describe this file - $Revision$ - $HeadURL$ - */ +*/ #ifndef LIBPARSE_H #define LIBPARSE_H @@ -11,9 +8,26 @@ #include #include #include +#include +#include #include -#include "mem.h" -#include "exn.h" +#include +#include + +/* Garbage Collection + *****************************************************************************/ +typedef void (*destructor_t)(void*); + +void gc_init(void** stack_bottom); +void gc_deinit(void); +void gc_collect(void); +void* gc_alloc(size_t size, destructor_t destructor); +void* gc_addref(void* ptr); +void gc_delref(void* ptr); +void gc_swapref(void** dest, void* newref); + +// Redfine main +extern int user_main(int argc, char** argv); /* Token Types *****************************************************************************/ @@ -151,8 +165,6 @@ char ident_value(AST* val); /* Lexer and Parser Types *****************************************************************************/ -DECLARE_EXCEPTION(ParseException); - typedef struct { char* line; size_t index; diff --git a/source/libparse/parser.c b/source/libparse/parser.c index 35323ce..a5e81ac 100644 --- a/source/libparse/parser.c +++ b/source/libparse/parser.c @@ -6,21 +6,19 @@ */ #include -DEFINE_EXCEPTION(ParseException, &RuntimeException); - Tok tok_eof = { NULL, 0, 0, T_END_FILE, {0} }; static void parser_free(void* obj) { Parser* parser = (Parser*)obj; if ((NULL != parser->tok) && (&tok_eof != parser->tok)) { - mem_release(parser->tok); + gc_delref(parser->tok); } - //mem_release(parser->stack); + //gc_delref(parser->stack); } Parser* parser_new(char* prompt, FILE* input) { - Parser* parser = (Parser*)mem_allocate(sizeof(Parser), &parser_free); + Parser* parser = (Parser*)gc_alloc(sizeof(Parser), &parser_free); parser->line = NULL; parser->index = 0; parser->lineno = 0; @@ -51,7 +49,7 @@ bool parser_eof(Parser* parser) { void parser_resume(Parser* parser) { if ((NULL != parser->tok) && (&tok_eof != parser->tok)) { - mem_release(parser->tok); + gc_delref(parser->tok); parser->tok = NULL; } //vec_clear(parser->stack); @@ -65,7 +63,7 @@ void error(Parser* parser, const char* text) (void)parser; Tok* tok = peek(parser); fprintf(stderr, ":%zu:%zu:Error: %s\n", tok->line, tok->col, text); - throw_msg(ParseException, text); + exit(1); } Tok* shifttok(Parser* parser, TokType type) @@ -84,7 +82,7 @@ bool accept(Parser* parser, TokType type) { bool ret = false; if (peek(parser)->type == type) { - mem_swap((void**)&(parser->tok), NULL); + gc_swapref((void**)&(parser->tok), NULL); ret = true; } return ret; @@ -94,7 +92,7 @@ bool accept_str(Parser* parser, TokType type, const char* text) { bool ret = false; if ((peek(parser)->type == type) && (0 == strcmp((char*)(parser->tok->value.text), text))) { - mem_swap((void**)&(parser->tok), NULL); + gc_swapref((void**)&(parser->tok), NULL); ret = true; } return ret; diff --git a/source/sclpl/main.c b/source/sclpl/main.c index df9299d..7d0e6fc 100644 --- a/source/sclpl/main.c +++ b/source/sclpl/main.c @@ -1,3 +1,4 @@ +#include #include /* Command Line Options @@ -70,7 +71,7 @@ static int emit_program(void) { * Implement name mangling algorithm for files and identifiers */ -int main(int argc, char **argv) { +int user_main(int argc, char **argv) { opts_parse( Options_Config, argc, argv ); if (!opts_is_set(NULL,"mode")) { print_usage(); -- 2.52.0