Index: .gitignore =================================================================== --- .gitignore (revision bd8540001c298d12d68dabcd274a24ed5a4dfb7a) +++ .gitignore (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -12,4 +12,7 @@ libcfa/Makefile src/Makefile + +# genereted by premake +src/examples/gc_no_raii/build # build directories Index: src/examples/gc_no_raii/bug-repro/assert.c =================================================================== --- src/examples/gc_no_raii/bug-repro/assert.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/bug-repro/assert.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,16 @@ +struct gc_object_header{ + int size; +}; + +struct gc_state; + +inline _Bool needs_collect(gc_state* state) { + return state->used_space > 0; +} + +struct gc_object_header* gc_get_object_for_ref(); + +inline gc_object_header* gc_get_object_ptr(void* ptr) +{ + return 0; +} Index: src/examples/gc_no_raii/bug-repro/crash.c =================================================================== --- src/examples/gc_no_raii/bug-repro/crash.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/bug-repro/crash.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,6 @@ + +void f() +{ + void* obj; + (void)obj; +} Index: src/examples/gc_no_raii/bug-repro/not_equal.c =================================================================== --- src/examples/gc_no_raii/bug-repro/not_equal.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/bug-repro/not_equal.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,10 @@ + +struct pointer_t +{ + void* p; +}; + +_Bool operator_not_equal_p(pointer_t* lhs, pointer_t* rhs) +{ + return lhs->p == rhs->p; +} Index: src/examples/gc_no_raii/cfa =================================================================== --- src/examples/gc_no_raii/cfa (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/cfa (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,1 @@ +../../../bin/cfa Index: src/examples/gc_no_raii/out.test =================================================================== --- src/examples/gc_no_raii/out.test (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/out.test (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,3 @@ +CFA Version 1.0.0 (debug) +make[1]: *** [debug/gcpointers.o] Error 1 +make: *** [gc-test] Error 2 Index: src/examples/gc_no_raii/pool-alloc/allocate-malign.c =================================================================== --- src/examples/gc_no_raii/pool-alloc/allocate-malign.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/pool-alloc/allocate-malign.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,30 @@ +/* + * Allocation functions (posix_malign) + * + * Copyright (c) 2014, 2015 Gregor Richards + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +static void *allocPool(size_t size, int mustSucceed) +{ + void *ret; + if ((errno = posix_memalign(&ret, size, size))) { + if (mustSucceed) { + perror("posix_memalign"); + abort(); + } + return NULL; + } + return ret; +} Index: src/examples/gc_no_raii/pool-alloc/allocate-malloc.c =================================================================== --- src/examples/gc_no_raii/pool-alloc/allocate-malloc.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/pool-alloc/allocate-malloc.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,53 @@ +/* + * Allocation functions (malloc) + * + * Copyright (c) 2014, 2015 Gregor Richards + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +static void *allocPool(int mustSucceed) +{ + static ggc_mutex_t poolLock = GGC_MUTEX_INITIALIZER; + static unsigned char *space = NULL, *spaceEnd = NULL; + void *ret; + + /* do we already have some available space? */ + ggc_mutex_lock_raw(&poolLock); + if (!space || space + GGGGC_POOL_BYTES > spaceEnd) { + ggc_size_t i; + + /* since we can't pre-align, align by getting as much as we can manage */ + for (i = 16; i >= 2; i /= 2) { + space = malloc(GGGGC_POOL_BYTES * i); + if (space) break; + } + if (!space) { + if (mustSucceed) { + perror("malloc"); + abort(); + } + return NULL; + } + spaceEnd = space + GGGGC_POOL_BYTES * i; + + /* align it */ + space = (unsigned char *) GGGGC_POOL_OF(space + GGGGC_POOL_BYTES - 1); + } + + ret = (struct GGGGC_Pool *) space; + space += GGGGC_POOL_BYTES; + ggc_mutex_unlock(&poolLock); + + return ret; +} Index: src/examples/gc_no_raii/pool-alloc/allocate-mmap.c =================================================================== --- src/examples/gc_no_raii/pool-alloc/allocate-mmap.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/pool-alloc/allocate-mmap.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,44 @@ +/* + * Allocation functions (mmap) + * + * Copyright (c) 2014, 2015 Gregor Richards + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +static void *allocPool(int mustSucceed) +{ + unsigned char *space, *aspace; + struct GGGGC_Pool *ret; + + /* allocate enough space that we can align it later */ + space = mmap(NULL, GGGGC_POOL_BYTES*2, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANON, -1, 0); + if (space == NULL) { + if (mustSucceed) { + perror("mmap"); + abort(); + } + return NULL; + } + + /* align it */ + ret = GGGGC_POOL_OF(space + GGGGC_POOL_BYTES - 1); + aspace = (unsigned char *) ret; + + /* free unused space */ + if (aspace > space) + munmap(space, aspace - space); + munmap(aspace + GGGGC_POOL_BYTES, space + GGGGC_POOL_BYTES - aspace); + + return ret; +} Index: src/examples/gc_no_raii/pool-alloc/allocate-win-valloc.c =================================================================== --- src/examples/gc_no_raii/pool-alloc/allocate-win-valloc.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/pool-alloc/allocate-win-valloc.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,45 @@ +/* + * Allocation functions (mmap) + * + * Copyright (c) 2014, 2015 Gregor Richards + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +static void *allocPool(int mustSucceed) +{ + unsigned char *space, *aspace; + struct GGGGC_Pool *ret; + + /* allocate enough space that we can align it later */ + space = (unsigned char *) + VirtualAlloc(NULL, GGGGC_POOL_BYTES*2, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE); + if (space == NULL) { + if (mustSucceed) { + perror("mmap"); + abort(); + } + return NULL; + } + + /* align it */ + ret = GGGGC_POOL_OF(space + GGGGC_POOL_BYTES - 1); + aspace = (unsigned char *) ret; + + /* free unused space */ + if (aspace > space) + VirtualFree(space, aspace - space, MEM_RELEASE); + VirtualFree(aspace + GGGGC_POOL_BYTES, space + GGGGC_POOL_BYTES - aspace, MEM_RELEASE); + + return ret; +} Index: src/examples/gc_no_raii/premake4.lua =================================================================== --- src/examples/gc_no_raii/premake4.lua (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/premake4.lua (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,76 @@ +#!lua + +-- Additional Linux libs: "X11", "Xxf86vm", "Xi", "Xrandr", "stdc++" + +includeDirList = { + "src/", + "../", +} + +libDirectories = { + +} + + +if os.get() == "linux" then + linkLibs = { + + } +end + +-- Build Options: +buildOptions = {""} + +solution "GC-no-RAII" + configurations { "debug", "release", + "cproc-debug", "cproc-release", + "cfa-debug", "cfa-release" } + + project "gc-test" + kind "ConsoleApp" + language "C" + location "build" + objdir "build" + targetdir "." + buildoptions (buildOptions) + defines { "bool=_Bool", + "\"true=((_Bool)(const signed int)1)\"", + "\"false=((_Bool)(const signed int)0)\"", + "_GNU_SOURCE"} + libdirs (libDirectories) + links (linkLibs) + linkoptions (linkOptionList) + includedirs (includeDirList) + files { "../fstream.c", "../iostream.c", "../iterator.c", "src/**.c" } + + configuration "debug" + defines { "DEBUG" } + flags { "Symbols" } + + configuration "release" + defines { "NDEBUG" } + flags { "Optimize" } + + configuration "cproc-debug" + buildoptions ({"-E"}) + linkoptions ({"-E"}) + defines { "DEBUG" } + flags { "Symbols" } + + configuration "cproc-release" + buildoptions ({"-E"}) + linkoptions ({"-E"}) + defines { "DEBUG" } + flags { "Symbols" } + + configuration "cfa-debug" + linkoptions ({"-E"}) + files { "build/cproc-debug/*.o" } + defines { "DEBUG" } + flags { "Symbols" } + + configuration "cfa-release" + linkoptions ({"-E"}) + files { "build/cproc-debug/*.o" } + defines { "DEBUG" } + flags { "Symbols" } Index: src/examples/gc_no_raii/regen_makefile.sh =================================================================== --- src/examples/gc_no_raii/regen_makefile.sh (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/regen_makefile.sh (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,6 @@ +#!/bin/sh + +premake4 clean +premake4 gmake +sed '/# GNU Make project makefile autogenerated by Premake/a CC = ..\/cfa\nCXX = ..\/cfa\n' build/Makefile > out +mv out build/Makefile Index: src/examples/gc_no_raii/src/allocate-pool.c =================================================================== --- src/examples/gc_no_raii/src/allocate-pool.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/allocate-pool.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,63 @@ +#define _BSD_SOURCE /* for MAP_ANON */ +#define _DARWIN_C_SOURCE /* for MAP_ANON on OS X */ + + +/* for standards info */ +#if defined(unix) || defined(__unix) || defined(__unix__) || \ + (defined(__APPLE__) && defined(__MACH__)) +#include +#endif + +#if defined(_WIN32) +#ifndef WIN32_LEAN_AND_MEAN +#define WIN32_LEAN_AND_MEAN +#endif +#include +#endif + +#include +#include +#include +#include +#include + +#if _POSIX_VERSION +#include +#endif + +#ifdef CFA +extern "C"{ +#endif + +/* figure out which allocator to use */ +#if defined(GGGGC_USE_MALLOC) +#define GGGGC_ALLOCATOR_MALLOC 1 +#include "../pool-alloc/allocate-malloc.c" + +#elif _POSIX_ADVISORY_INFO >= 200112L +#define GGGGC_ALLOCATOR_POSIX_MEMALIGN 1 +#include "../pool-alloc/allocate-malign.c" + +#elif defined(MAP_ANON) +#define GGGGC_ALLOCATOR_MMAP 1 +#include "../pool-alloc/allocate-mmap.c" + +#elif defined(_WIN32) +#define GGGGC_ALLOCATOR_VIRTUALALLOC 1 +#include "../pool-alloc/allocate-win-valloc.c" + +#else +#warning GGGGC: No allocator available other than malloc! +#define GGGGC_ALLOCATOR_MALLOC 1 +#include "../pool-alloc/allocate-malloc.c" + +#endif + +void* pal_allocPool(size_t size, int mustSucceed) +{ + return allocPool(size, mustSucceed); +} + +#ifdef CFA +} +#endif Index: src/examples/gc_no_raii/src/allocate-pool.h =================================================================== --- src/examples/gc_no_raii/src/allocate-pool.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/allocate-pool.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,14 @@ +#ifndef _GGGGC_ALlOCATE_POOL_H_ +#define _GGGGC_ALlOCATE_POOL_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +void* pal_allocPool(size_t size, int mustSucceed); + +#ifdef __cplusplus +} +#endif + +#endif Index: src/examples/gc_no_raii/src/gc.h =================================================================== --- src/examples/gc_no_raii/src/gc.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/gc.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,9 @@ +#pragma once + +#include "gcpointers.h" + +// forall( dtype T ) +// gcpointer_t gcmalloc() +// { +// +// } Index: src/examples/gc_no_raii/src/gcpointers.c =================================================================== --- src/examples/gc_no_raii/src/gcpointers.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/gcpointers.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,101 @@ +#include "gcpointers.h" + +#include "gc.h" +#include "internal/collector.h" +#include "internal/object_header.h" +// #include "internal/state.h" + +void register_ptr(gcpointer_t* this) +{ + if(gcpointer_null(this)) return; + + _Bool managed = gc_is_managed(this); + + if(managed) + { + gc_object_header* obj = gc_get_object_for_ref(gc_get_state(), (void*)this); + check(obj); + check(gc_obj_is_valide(obj)); + check(gc_is_managed(this) == gc_is_managed(obj->type_chain) || obj->type_chain == NULL); + this->next = obj->type_chain; + obj->type_chain = this; + check(obj->is_valide()); + } + else + { + gc_object_header* obj = gc_get_object_ptr((void*)this->ptr); + check(obj); + check(gc_obj_is_valide(obj)); + check(gc_is_managed(this) == gc_is_managed(obj->root_chain) || obj->root_chain == NULL); + this->next = obj->root_chain; + obj->root_chain = this; + check(gc_obj_is_valide(obj)); + } +} + +void unregister_ptr(gcpointer_t* this) +{ + if(gcpointer_null(this)) return; + + gcpointer_t** prev_next_ptr = gc_find_previous_ref(this); + check((*prev_next_ptr) == this); + + (*prev_next_ptr) = this->next; +} + +void gcpointer_ctor(gcpointer_t* this) +{ + this->ptr = (intptr_t)NULL; + this->next = NULL; +} + +void gcpointer_ctor(gcpointer_t* this, void* address) +{ + this->ptr = (intptr_t)address; + this->next = NULL; + + register_ptr(this); +} + +void gcpointer_ctor(gcpointer_t* this, gcpointer_t* other) +{ + this->ptr = other->ptr; + this->next = NULL; + + register_ptr(this); +} + +void gcpointer_dtor(gcpointer_t* this) +{ + unregister_ptr(this); +} + +gcpointer_t* gcpointer_assign(gcpointer_t* this, gcpointer_t* rhs) +{ + if(this != rhs) + { + unregister_ptr(this); + + this->ptr = rhs->ptr; + + register_ptr(this); + } + + return this; +} + +//Logical operators +int gcpointer_equal(gcpointer_t* this, gcpointer_t* rhs) +{ + return this->ptr == rhs->ptr; +} + +int gcpointer_not_equal(gcpointer_t* this, gcpointer_t* rhs) +{ + return this->ptr != rhs->ptr; +} + +int gcpointer_null(gcpointer_t* this) +{ + return this->ptr == (intptr_t)NULL; +} Index: src/examples/gc_no_raii/src/gcpointers.h =================================================================== --- src/examples/gc_no_raii/src/gcpointers.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/gcpointers.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,23 @@ +#pragma once + +#include + +struct gcpointer_t +{ + intptr_t ptr; + struct gcpointer_t* next; +}; + +void gcpointer_ctor(gcpointer_t* this); +// void gcpointer_ctor(gcpointer_t* ptr, (int)0); +void gcpointer_ctor(gcpointer_t* this, void* address); +void gcpointer_ctor(gcpointer_t* this, gcpointer_t* other); + +void gcpointer_dtor(gcpointer_t* this); + +gcpointer_t* gcpointer_assign(gcpointer_t* this, gcpointer_t* rhs); + +//Logical operators +int gcpointer_equal(gcpointer_t* this, gcpointer_t* rhs); +int gcpointer_not_equal(gcpointer_t* this, gcpointer_t* rhs); +int gcpointer_null(gcpointer_t* this); Index: src/examples/gc_no_raii/src/gctest.c =================================================================== --- src/examples/gc_no_raii/src/gctest.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/gctest.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,9 @@ + +#include "gc.h" +#include "fstream.h" + +int main() { + ofstream *sout = ofstream_stdout(); + ifstream *sin = ifstream_stdin(); + sout | "Bonjour au monde!\n"; +} Index: src/examples/gc_no_raii/src/internal/collector.c =================================================================== --- src/examples/gc_no_raii/src/internal/collector.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/internal/collector.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,142 @@ +#include "collector.h" + +#include +#include +#include +#include + +#include "fstream.h" + +#include "memory_pool.h" + +void* gc_finish_alloc_block(void* block, size_t actual_size, size_t target_size); +void gc_assign_reference(void** ref, gc_object_header* ptr); + +gcpointer_t** gc_find_previous_ref(gcpointer_t* target) +{ + if(!(target)) return NULL; + + bool managed = gc_is_managed(target); + gc_object_header* obj = gc_get_object_ptr((void*)target->ptr); + + check(gc_is_valide(obj)); + + gcpointer_t** prev_next_ptr = managed ? &obj->type_chain : &obj->root_chain; + while((*prev_next_ptr) && (*prev_next_ptr) != target) + { + prev_next_ptr = &(*prev_next_ptr)->next; + } + + return prev_next_ptr; +} + +void* gc_allocate(size_t target_size) +{ + size_t size = gc_compute_size(target_size + sizeof(gc_object_header)); + + check(size < POOL_SIZE_BYTES); + + void* block = NULL; + gc_state* gc = gc_get_state(); + + if((intptr_t)(block = gc_try_allocate(gc, size))) return gc_finish_alloc_block(block, size, target_size); + + gc_collect(gc); + + if((intptr_t)(block = gc_try_allocate(gc, size))) return gc_finish_alloc_block(block, size, target_size); + + gc_allocate_pool(gc); + + if((intptr_t)(block = gc_try_allocate(gc, size))) return gc_finish_alloc_block(block, size, target_size); + + ofstream_stderr() | "ERROR: allocation in new pool failed" | endl; + abort(); + + return NULL; +} + +void* gc_finish_alloc_block(void* block, size_t actual_size, size_t target_size) +{ + void* data = (void*)(((intptr_t)block) + sizeof(gc_object_header)); + void* header = block; + + check(((intptr_t)data) > ((intptr_t)block)); + check(((intptr_t)data) >= ((intptr_t)header)); + check(is_aligned(data)); + check(((intptr_t)data) + target_size <= ((intptr_t)block) + actual_size); + + gc_object_header* obj = gc_object_header_placement_ctor(header, actual_size); + + // (void)obj; //remove unsused warning since this is for debug + check(obj == get_object_ptr(data)); + + gc_register_allocation(gc_get_state(), actual_size); + + return data; +} + +void gc_process_reference(void** ref, worklist_t* worklist) +{ + check(!gc_is_in_heap(gc_get_state(), ref)); + + gc_object_header* ptr = gc_get_object_ptr(*ref); + if(ptr) + { + if(!ptr->is_forwarded) + { + gc_copy_object(ptr); + + gc_scan_object(ptr->forward, worklist); + + gc_assign_reference(ref, ptr->forward); + } + else + { + //duplication to help debug + gc_assign_reference(ref, ptr->forward); + } + } +} + +void gc_assign_reference(void** ref, gc_object_header* ptr) +{ + void* address = (void*)(((intptr_t)ptr) + sizeof(gc_object_header)); + + gc_write_aligned_ptr(ref, address); +} + +gc_object_header* gc_copy_object(gc_object_header* ptr) +{ + check(!ptr->forward); + check(!ptr->is_forwarded); + check(gc_is_from_space(gc_pool_of(ptr))); + + gc_memory_pool* pool = gc_pool_of(ptr)->mirror; + + void* new_block = gc_pool_allocate(pool, ptr->size, true); + + memcpy(new_block, ptr, ptr->size); + + gc_object_header* fwd_ptr = gc_object_header_placement_copy_ctor(new_block, ptr); + + ptr->forward = fwd_ptr; + ptr->is_forwarded = true; + + return fwd_ptr; +} + +void gc_scan_object(gc_object_header* object, worklist_t* worklist) +{ + gcpointer_t* field = object->type_chain; + while(field) + { + check(((intptr_t)field) > ((intptr_t)object)); + check(((intptr_t)field) < ((intptr_t)((intptr_t)object) + object->size)); + + check(gc_is_in_to_space(gc_get_state(), &type->ptr)); + + push_back(worklist, &field->ptr); + + field = field->next; + } +} Index: src/examples/gc_no_raii/src/internal/collector.h =================================================================== --- src/examples/gc_no_raii/src/internal/collector.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/internal/collector.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,48 @@ +#pragma once + +#include +#include + +#include "tools.h" + +#include "gcpointers.h" +#include "internal/collector.h" +#include "internal/gc_tools.h" +#include "internal/globals.h" +#include "internal/object_header.h" +#include "internal/state.h" +#include "tools/worklist.h" + +inline bool gc_is_managed(void* address) +{ + return gc_is_in_heap(gc_get_state(), address); +} + +inline gc_object_header* gc_get_object_ptr(void* ptr) +{ + void* clean = gc_get_aligned_ptr(ptr); + return ((gc_object_header*)clean) - 1; +} + +inline gc_memory_pool* gc_pool_of(void* address) +{ + return (struct gc_memory_pool*)(((intptr_t)address) & POOL_PTR_MASK); +} + +inline void gc_conditional_collect() +{ + if(gc_needs_collect(gc_get_state())) + { + gc_collect(gc_get_state()); + } +} + +gcpointer_t** gc_find_previous_ref(gcpointer_t* target); + +void* gc_allocate(size_t size); + +void gc_process_reference(void** ref, worklist_t* worklist); + +struct gc_object_header* gc_copy_object(struct gc_object_header* ptr); + +void gc_scan_object(struct gc_object_header* object, worklist_t* worklist); Index: src/examples/gc_no_raii/src/internal/gc_tools.h =================================================================== --- src/examples/gc_no_raii/src/internal/gc_tools.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/internal/gc_tools.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,40 @@ +#pragma once + +#include +#include + +#include "tools.h" +#include "globals.h" + +inline bool gc_is_aligned(void* address) +{ + return (((intptr_t)address) & (~OBJECT_PTR_MASK)) == 0; +} + +inline void* gc_get_aligned_ptr(void* address) +{ + return (void*)(((intptr_t)address) & (OBJECT_PTR_MASK)); +} + +inline void* gc_write_aligned_ptr(void** reference, void* address) +{ + size_t ref_last_bits = ((intptr_t)*reference) & (~OBJECT_PTR_MASK); + + size_t new_val = ((intptr_t)address) & OBJECT_PTR_MASK; + + (*reference) = (void*)(new_val | ref_last_bits); + + return *reference; +} + +inline size_t gc_compute_size(size_t size) +{ + size_t word_size = ((size - 1) / OBJECT_ALLIGNMENT) + 1; + size_t ret = word_size * OBJECT_ALLIGNMENT; + + check(ret >= size); + check((ret % OBJECT_ALLIGNMENT) == 0); + check( ((size % OBJECT_ALLIGNMENT) != 0) || (ret == size) ); + + return ret; +} Index: src/examples/gc_no_raii/src/internal/globals.h =================================================================== --- src/examples/gc_no_raii/src/internal/globals.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/internal/globals.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,29 @@ +#pragma once + +// #include +// #include +// +// static const size_t POOL_SIZE_EXP = 24; +// static const size_t POOL_SIZE_BYTES = 0x1 << POOL_SIZE_EXP; +// static const size_t POOL_PTR_MASK = ~(POOL_SIZE_BYTES - 1); +// +// static const size_t CARDS_SIZE_EXP = 12; +// static const size_t CARDS_SIZE_BYTES = 0x1 << CARDS_SIZE_EXP; +// static const size_t CARDS_OFFSET_MASK = (~(CARDS_SIZE_BYTES - 1)) & (POOL_SIZE_BYTES - 1); +// static const size_t CARDS_COUNT = POOL_SIZE_BYTES / CARDS_SIZE_BYTES; +// +// static const size_t OBJECT_ALLIGNMENT = sizeof(size_t); +// static const size_t OBJECT_PTR_MASK = ~(OBJECT_ALLIGNMENT - 1); + + +#define POOL_SIZE_EXP 24 +#define POOL_SIZE_BYTES 0x1 << POOL_SIZE_EXP +#define POOL_PTR_MASK ~(POOL_SIZE_BYTES - 1) + +#define CARDS_SIZE_EXP 12 +#define CARDS_SIZE_BYTES 0x1 << CARDS_SIZE_EXP +#define CARDS_OFFSET_MASK (~(CARDS_SIZE_BYTES - 1)) & (POOL_SIZE_BYTES - 1) +#define CARDS_COUNT POOL_SIZE_BYTES / CARDS_SIZE_BYTES + +#define OBJECT_ALLIGNMENT sizeof(size_t) +#define OBJECT_PTR_MASK ~(OBJECT_ALLIGNMENT - 1) Index: src/examples/gc_no_raii/src/internal/memory_pool.h =================================================================== --- src/examples/gc_no_raii/src/internal/memory_pool.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/internal/memory_pool.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,74 @@ +#pragma once + +#include + +#include "tools.h" + +// #include "card_table.h" +#include "collector.h" +#include "globals.h" + +typedef int cardtable_ptr_t; + +struct gc_memory_pool +{ + struct memory_pool* mirror; + struct memory_pool* next; + + uint8_t type_code; + + cardtable_ptr_t cards; + + uint8_t* end_p; + uint8_t* free_p; + uint8_t start_p[1]; +}; + +struct gc_pool_object_iterator +{ + + struct gc_object_header* object; + #if _DEBUG + intptr_t lower_limit; + intptr_t upper_limit; + #endif +}; + + +void gc_pool_object_iterator_ctor( + struct gc_object_header* start_object + #if _DEBUG + , intptr_t pool_start + , intptr_t pool_end + #endif + ); + +bool ?!=?(const gc_pool_object_iterator lhs, const gc_pool_object_iterator rhs); + +gc_pool_object_iterator* ++?(gc_pool_object_iterator* it); + +const struct gc_object_header* *?(const gc_pool_object_iterator it); +struct gc_object_header* *?(gc_pool_object_iterator it); + +inline bool gc_pool_is_from_space(const gc_memory_pool* pool) +{ + return gc_from_space_code(gc_get_state()) == pool->type_code; +} + +void gc_reset_pool(gc_memory_pool* pool); + +inline size_t gc_pool_size_total(const gc_memory_pool* pool) +{ + return pool->end_p - pool->start_p; +} + +inline size_t gc_pool_size_left(const gc_memory_pool* pool) +{ + return pool->end_p - pool->free_p; +} + +void* gc_pool_allocate(gc_memory_pool* pool, size_t size, bool zero); + +gc_pool_object_iterator gc_pool_iterator_for(gc_memory_pool* pool, void* member); + +gc_pool_object_iterator gc_pool_end(gc_memory_pool* pool); Index: src/examples/gc_no_raii/src/internal/object_header.h =================================================================== --- src/examples/gc_no_raii/src/internal/object_header.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/internal/object_header.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,33 @@ +#pragma once + +#include +#include + +#include "tools.h" + +#if DEBUG + static const void* CANARY_VALUE = (void*)0xCAFEBABACAFEBABA; +#endif + +struct gcpointer_t; +struct gc_object_header; + +struct gc_object_header +{ + #if DEBUG + void* canary_start; + #endif + + size_t size; + gcpointer_t* root_chain; + gcpointer_t* type_chain; + gc_object_header* forward; + bool is_forwarded; + + #if DEBUG + void* canary_end; + #endif +}; + +gc_object_header* gc_object_header_placement_ctor(void* address, size_t size); +gc_object_header* gc_object_header_placement_copy_ctor(void* address, gc_object_header* other); Index: src/examples/gc_no_raii/src/internal/state.c =================================================================== --- src/examples/gc_no_raii/src/internal/state.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/internal/state.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,277 @@ +#include "state.h" + +#include + +//general purpouse includes +#include "tools.h" + +//platform abstraction includes +#include "allocate-pool.h" + +//gc internal includes +// #include "globals.h" +#include "memory_pool.h" +// #include "memory_pool_iterator.h" +// #include "object_header.h" +// +// void swap(gc_state* state); +// void sweep_roots(worklist_t worklist); +// void clear(gc_state* state); +// void calc_usage(gc_state* state); +// +// #if DEBUG +// bool roots_match(gc_state* state); +// bool no_from_space_ref(gc_state* state); +// #endif + +void gc_state_ctor(gc_state* state) +{ + state->from_code = 0; + state->to_space = NULL; + state->from_space = NULL; + state->total_space = 0; + state->used_space = 0; + // state->pools_table(); + + gc_allocate_pool(state); + + state->is_initialized = true; +} + +// bool state::is_in_heap(void* address) const +// { +// memory_pool* target_pool = gc_pool_of(address); +// +// auto first = pools_table.cbegin(); +// auto last = pools_table.cend(); +// auto result = std::find(first, last, target_pool); +// return result != last && (*result)->is_from_space(); +// } + +// bool state::is_in_to_space(void* address) const +// { +// const memory_pool* target_pool = pool_of(address); +// +// auto first = pools_table.cbegin(); +// auto last = pools_table.cend(); +// auto result = std::find(first, last, target_pool); +// return result != last && !(*result)->is_from_space(); +// } +// +gc_object_header* gc_get_object_for_ref(gc_state* state, void* member) +{ + intptr_t target = ((intptr_t)member); + if(!gc_is_in_heap(state, member)) return NULL; + + gc_memory_pool* pool = gc_pool_of(member); + gc_pool_object_iterator it = gc_pool_iterator_for(pool, member); + gc_pool_object_iterator end = gc_pool_end(pool); + + while(it != end) + { + gc_object_header* object = *it; + { + intptr_t start = ((intptr_t)object); + intptr_t end = ((intptr_t)start + object->size); + if(start < target && end > target) + { + return object; + } + } + ++it; + } + + checkf(false, "is_in_heap() and iterator_for() return inconsistent data"); + abort(); + return NULL; +} +// +// void* state::try_allocate(size_t size) +// { +// memory_pool* pool = from_space; +// while(pool) +// { +// if(pool->size_left() > size) +// { +// return pool->allocate(size, true); +// } +// pool = pool->next(); +// } +// +// return nullptr; +// } +// +// void state::allocate_pool() +// { +// memory_pool* old_from_space = from_space; +// memory_pool* old_to_space = to_space; +// +// from_space = reinterpret_cast(pal_allocPool(POOL_SIZE_BYTES, 1)); +// to_space = reinterpret_cast(pal_allocPool(POOL_SIZE_BYTES, 1)); +// +// new (from_space) memory_pool(POOL_SIZE_BYTES, old_from_space, to_space, from_code); +// new (to_space) memory_pool(POOL_SIZE_BYTES, old_to_space, from_space, (~from_code) & 0x01); +// +// total_space += from_space->size(); +// +// pools_table.push_back(from_space); +// pools_table.push_back(to_space); +// } +// +// void state::collect() +// { +// DEBUG("collecting"); +// DEBUG("previous usage " << used_space << " / " << total_space); +// +// std::vector worklist; +// sweep_roots(worklist); +// +// while(!worklist.empty()) +// { +// void** ref = worklist.back(); +// worklist.pop_back(); +// process_reference(ref, worklist); +// } +// +// check(roots_match()); +// check(no_from_space_ref()); +// +// swap(); +// +// calc_usage(); +// +// if(needs_collect()) allocate_pool(); +// +// DEBUG("done"); +// } +// +// void state::swap() +// { +// std::swap(from_space, to_space); +// +// memory_pool* pool = to_space; +// while(pool) +// { +// pool->reset(); +// pool = pool->next(); +// } +// +// from_code = (~from_code) & 0x01; +// +// #if _DEBUG +// { +// memory_pool* pool = from_space; +// while(pool) +// { +// check(pool->is_from_space()); +// pool = pool->next(); +// } +// +// pool = to_space; +// while(pool) +// { +// check(!pool->is_from_space()); +// pool = pool->next(); +// } +// } +// #endif +// } +// +// void state::sweep_roots(std::vector& worklist) +// { +// memory_pool* pool = from_space; +// while(pool) +// { +// for(object_header* object : *pool) +// { +// if(!object->root_chain) continue; +// +// copy_object(object); +// +// scan_object(object->forward, worklist); +// } +// +// pool = pool->next(); +// } +// } +// +// void state::clear() +// { +// memory_pool* pool = from_space; +// while(pool) +// { +// pool->reset(); +// pool = pool->next(); +// } +// +// pool = to_space; +// while(pool) +// { +// pool->reset(); +// pool = pool->next(); +// } +// } +// +// void state::calc_usage() +// { +// total_space = 0; +// used_space = 0; +// +// memory_pool* pool = from_space; +// while(pool) +// { +// size_t size = pool->size(); +// size_t used = size - pool->size_left(); +// check(used <= size); +// total_space += size; +// used_space += used; +// +// pool = pool->next(); +// } +// } +// +// #if _DEBUG +// bool state::roots_match() +// { +// memory_pool* pool = to_space; +// while(pool) +// { +// size_t size = 0; +// for(object_header* object : *pool) +// { +// size += object->size; +// +// gcpointer_base* ptr = object->root_chain; +// while(ptr) +// { +// check(get_object_ptr(ptr->m_ptr) == object); +// ptr = ptr->m_next; +// } +// } +// +// check(size + pool->size_left() == pool->size()); +// +// pool = pool->next(); +// } +// +// return true; +// } +// +// bool state::no_from_space_ref() +// { +// memory_pool* pool = to_space; +// while(pool) +// { +// void** potential_ref = (void**)pool->m_start; +// while(potential_ref < (void**)pool->m_free) +// { +// check(!is_in_heap(*potential_ref)); +// potential_ref++; +// } +// +// pool = pool->next(); +// } +// +// return true; +// } +// #endif Index: src/examples/gc_no_raii/src/internal/state.h =================================================================== --- src/examples/gc_no_raii/src/internal/state.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/internal/state.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,56 @@ +#pragma once + +#include +#include + +#include "tools.h" + +struct gc_state +{ + bool is_initialized; + uint8_t from_code; + struct gc_memory_pool* to_space; + struct gc_memory_pool* from_space; + + size_t total_space; + size_t used_space; + + // const struct memory_pool* pools_table; + // size_t pools_table_count; +}; + +void gc_state_ctor(struct gc_state* state); + +static inline gc_state* gc_get_state() +{ + static gc_state s; + if(!s.is_initialized) gc_state_ctor(&s); + return &s; +} + +inline bool gc_needs_collect(gc_state* state) +{ + return state->used_space * 2 > state->total_space; +} + +void gc_collect(gc_state* state); + +void* gc_try_allocate(gc_state* state, size_t size); + +void gc_allocate_pool(gc_state* state); + +bool gc_is_in_heap(const gc_state* state, void* address); + +bool gc_is_in_to_space(const gc_state* state, void* address); + +inline uint8_t gc_from_space_code(const gc_state* state) +{ + return state->from_code; +} + +struct gc_object_header* gc_get_object_for_ref(gc_state* state, void*); + +inline void gc_register_allocation(gc_state* state, size_t size) +{ + state->used_space += size; +} Index: src/examples/gc_no_raii/src/tools.h =================================================================== --- src/examples/gc_no_raii/src/tools.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/tools.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,4 @@ +#pragma once + +#include "tools/checks.h" +#include "tools/print.h" Index: src/examples/gc_no_raii/src/tools/checks.h =================================================================== --- src/examples/gc_no_raii/src/tools/checks.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/tools/checks.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,27 @@ +#pragma once + +#if _DEBUG + +#include +#include + +#define check(x) do {\ + if(!(x)) {\ + printf("CHECK failed : %s at %s:%i\n", #x, __FILE__, __LINE__);\ + abort();\ + }}while(0)\ + +#define checkf(x, ...) do {\ + if(!(x)) {\ + printf("CHECK failed : %s at %s:%i\n", #x, __FILE__, __LINE__);\ + printf(__VA_ARGS__);\ + abort();\ + }}while(0)\ + +#else + +#define check(x) + +#define checkf(x, format, ...) + +#endif //NO_CHECKS Index: src/examples/gc_no_raii/src/tools/print.c =================================================================== --- src/examples/gc_no_raii/src/tools/print.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/tools/print.c (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,5 @@ +#include "tools.h" + +#if _DEBUG + ofstream *sout = ofstream_stdout(); +#endif Index: src/examples/gc_no_raii/src/tools/print.h =================================================================== --- src/examples/gc_no_raii/src/tools/print.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/tools/print.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,15 @@ +#pragma once + +#if _DEBUG + +#include "fstream.h" + +extern ofstream *sout; + +#define DEBUG_OUT(x) sout | x | endl; + +#else + +#define DEBUG_OUT(x) + +#endif //NO_CHECKS Index: src/examples/gc_no_raii/src/tools/worklist.h =================================================================== --- src/examples/gc_no_raii/src/tools/worklist.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) +++ src/examples/gc_no_raii/src/tools/worklist.h (revision d41280e1c786301d271ddcab3018dd33565e37b5) @@ -0,0 +1,14 @@ +#pragma once + +#include +#include + +typedef intptr_t* worklist_element_t; + +struct worklist_t +{ + size_t count; + worklist_element_t* data; +}; + +void push_back(worklist_t* worklist, worklist_element_t element);