Index: tests/zombies/gc_no_raii/src/internal/card_table.h =================================================================== --- tests/zombies/gc_no_raii/src/internal/card_table.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/card_table.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,62 @@ +#pragma once + +#include "globals.h" +#include "tools.h" + +static inline size_t card_of(void* address) +{ + size_t card = ( ((intptr_t)address) & CARDS_OFFSET_MASK ) >> CARDS_SIZE_EXP; + checkf(card < CARDS_COUNT, (const char*)"%lu %lu = (%lx & %lx) >> %lu\n", (size_t)CARDS_COUNT, (size_t)card, (size_t)address, (size_t)CARDS_OFFSET_MASK, (size_t)CARDS_SIZE_EXP); + check(card < CARDS_COUNT); + return card; +} + +struct card_table_t +{ + size_t count; + void* cards_start[CARDS_COUNT]; +}; + +static inline void ?{}(card_table_t* this) +{ + this->count = 0; +} + +static inline void ^?{}(card_table_t* this) +{ + +} + +static inline void* object_at(card_table_t* const this, size_t card_number) +{ + return card_number < this->count ? this->cards_start[card_number] : NULL; +} + +static inline void register_object(card_table_t* const this, void* object) +{ + size_t card = card_of(object); + if(card < this->count) + { + intptr_t card_obj_add = (intptr_t)object_at(this, card); + intptr_t obj_add = (intptr_t)object; + if(card_obj_add > obj_add) + { + this->cards_start[card] = object; + } + } + else + { + check(card == this->count); + this->count++; + this->cards_start[card] = object; + } +} + +static inline void reset(card_table_t* const this) +{ + for(size_t i = 0; i < this->count; i++) + { + this->cards_start[i] = NULL; + } + this->count = 0; +} Index: tests/zombies/gc_no_raii/src/internal/collector.c =================================================================== --- tests/zombies/gc_no_raii/src/internal/collector.c (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/collector.c (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,152 @@ +#include "collector.h" + +#ifdef __cforall +extern "C" { +#endif +#include +#ifdef __cforall +} +#endif + +#include + +#include "state.h" +#include "gcpointers.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(is_valid(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) +{ + // sout | "Allocating " | target_size | " bytes"; + + size_t size = gc_compute_size(target_size + sizeof(gc_object_header)); + + // sout | "Object header size: " | sizeof(gc_object_header) | " bytes"; + // sout | "Actual allocation size: " | size | " bytes"; + + 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); + + checkf( (int) 0, "ERROR: allocation in new pool failed"); + + return NULL; +} + +void* gc_finish_alloc_block(void* block, size_t actual_size, size_t target_size) +{ + intptr_t data = ((intptr_t)block) + sizeof(gc_object_header); + void* header = block; + + check( data > ((intptr_t)block)); + check( data >= ((intptr_t)header)); + check( gc_is_aligned( (void*)data ) ); + check( data + target_size <= ((intptr_t)block) + actual_size ); + + gc_object_header* obj = placement_ctor(header, actual_size); + + (void)obj; //remove unsused warning since this is for debug + check(obj == gc_get_object_ptr( (void*)data )); + + gc_register_allocation(gc_get_state(), actual_size); + + return (void*)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_pool_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 = 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(), &field->ptr)); + + intptr_t* ref = &field->ptr; + push_back(worklist, ref); + + field = field->next; + } +} Index: tests/zombies/gc_no_raii/src/internal/collector.h =================================================================== --- tests/zombies/gc_no_raii/src/internal/collector.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/collector.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,47 @@ +#pragma once + +#include + +#include "tools.h" +// +#include "gcpointers.h" +#include "state.h" +#include "internal/gc_tools.h" +#include "internal/globals.h" +#include "internal/object_header.h" +#include "internal/state.h" +#include "tools/worklist.h" + +static inline bool gc_is_managed(void* address) +{ + return gc_is_in_heap(gc_get_state(), address); +} + +static inline gc_object_header* gc_get_object_ptr(void* ptr) +{ + void* clean = gc_get_aligned_ptr(ptr); + return ((gc_object_header*)clean) - 1; +} + +static inline struct gc_memory_pool* gc_pool_of(void* address) +{ + return (struct gc_memory_pool*)(((intptr_t)address) & POOL_PTR_MASK); +} + +static 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: tests/zombies/gc_no_raii/src/internal/gc_tools.h =================================================================== --- tests/zombies/gc_no_raii/src/internal/gc_tools.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/gc_tools.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,40 @@ +#pragma once + +#include +#include + +#include "tools.h" +#include "globals.h" + +static inline bool gc_is_aligned(void* address) +{ + return (((intptr_t)address) & (~OBJECT_PTR_MASK)) == 0; +} + +static inline void* gc_get_aligned_ptr(void* address) +{ + return (void*)(((intptr_t)address) & (OBJECT_PTR_MASK)); +} + +static 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; +} + +static 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: tests/zombies/gc_no_raii/src/internal/globals.h =================================================================== --- tests/zombies/gc_no_raii/src/internal/globals.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/globals.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,30 @@ +#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); + +enum { + POOL_SIZE_EXP = 24, + POOL_SIZE_BYTES = 0x1 << POOL_SIZE_EXP, + POOL_PTR_MASK = ~(POOL_SIZE_BYTES - 1), + + CARDS_SIZE_EXP = 12, + CARDS_SIZE_BYTES = 0x1 << CARDS_SIZE_EXP, + CARDS_OFFSET_MASK = (~(CARDS_SIZE_BYTES - 1)) & (POOL_SIZE_BYTES - 1), + CARDS_COUNT = POOL_SIZE_BYTES / CARDS_SIZE_BYTES, + + OBJECT_ALLIGNMENT = sizeof(size_t), + OBJECT_PTR_MASK = ~(OBJECT_ALLIGNMENT - 1), +}; Index: tests/zombies/gc_no_raii/src/internal/memory_pool.c =================================================================== --- tests/zombies/gc_no_raii/src/internal/memory_pool.c (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/memory_pool.c (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,160 @@ +#include "memory_pool.h" + +extern "C" { + #include + #include +} + +#include "collector.h" +#include "object_header.h" + +const size_t gc_pool_header_size = (size_t)( &(((gc_memory_pool*)NULL)->start_p) ); + +void ?{}(gc_memory_pool* this, size_t size, gc_memory_pool* next, gc_memory_pool* mirror, uint8_t type) +{ + this->mirror = mirror; + this->next = next; + this->type_code = type; + + this->cards = ( (card_table_t*)malloc(sizeof(card_table_t)) ){}; + + this->end_p = ((uint8_t*)this) + size; + this->free_p = this->start_p; + + check( gc_pool_of( (void*)this ) == this); + check(this->cards); + gc_reset_pool(this); +} + +void ^?{}(gc_memory_pool* this) +{ + ^(&this->cards){}; + free(this->cards); +} + +void gc_reset_pool(gc_memory_pool *const this) +{ + this->free_p = this->start_p; + #ifndef NDEBUG + memset(this->start_p, 0xCD, gc_pool_size_total(this)); + #endif + + check(this->cards); + reset(this->cards); + + check(gc_pool_size_left(this) == gc_pool_size_total(this)); +} + +void* gc_pool_allocate(gc_memory_pool *const this, size_t size, bool zero) +{ + void* ret = this->free_p; + + this->free_p += size; + + if (zero) memset(ret, 0x00, size); + + check(this->cards); + register_object(this->cards, ret); + + return ret; +} + +void ?{}( gc_pool_object_iterator* this, + struct gc_object_header* start_object + #ifndef NDEBUG + , intptr_t pool_start + , intptr_t pool_end + #endif + ) +{ + this->object = start_object; + #ifndef NDEBUG + this->lower_limit = pool_start; + this->upper_limit = pool_end; + #endif + + check( ((intptr_t)start_object) >= this->lower_limit ); + check( ((intptr_t)start_object) <= this->upper_limit ); +} + +void ^?{}( gc_pool_object_iterator* this ) {} + +gc_pool_object_iterator gc_pool_iterator_for(gc_memory_pool* const this, void* member) +{ + size_t card = card_of(member); + intptr_t member_add = (intptr_t)member; + intptr_t start_obj; + + do + { + check(card < CARDS_COUNT); + start_obj = (intptr_t)object_at(this->cards, card); + check(card != 0 || start_obj); + card--; + } + while(start_obj > member_add || !(start_obj)); + + check( start_obj ); + + struct gc_object_header* start_obj_typed = (struct gc_object_header*)start_obj; + + return (gc_pool_object_iterator) { + start_obj_typed + #ifndef NDEBUG + , (intptr_t)this->start_p + , (intptr_t)this->free_p + #endif + }; +} + +bool ?!=?(const gc_pool_object_iterator lhs, const gc_pool_object_iterator rhs) +{ + return lhs.object != rhs.object; +} + +gc_pool_object_iterator begin(gc_memory_pool* const this) +{ + struct gc_object_header* start_obj = (struct gc_object_header*)this->start_p; + return (gc_pool_object_iterator) { + start_obj + #ifndef NDEBUG + , (intptr_t)this->start_p + , (intptr_t)this->free_p + #endif + }; +} + +gc_pool_object_iterator end(gc_memory_pool* const this) +{ + return (gc_pool_object_iterator) { + (struct gc_object_header*)this->free_p + #ifndef NDEBUG + , (intptr_t)this->start_p + , (intptr_t)this->free_p + #endif + }; +} + +gc_pool_object_iterator* ++?(gc_pool_object_iterator* it) +{ + struct gc_object_header* object = it->object; + intptr_t next_ptr = ((intptr_t)object) + object->size; + check(next_ptr > it->lower_limit); + check(next_ptr <= it->upper_limit); + + struct gc_object_header* next_obj = ((struct gc_object_header*)next_ptr); + check(next_ptr == it->upper_limit || is_valid(next_obj)); + + it->object = next_obj; + return it; +} + +const struct gc_object_header* *?(const gc_pool_object_iterator it) +{ + return it.object; +} + +struct gc_object_header* *?(gc_pool_object_iterator it) +{ + return it.object; +} Index: tests/zombies/gc_no_raii/src/internal/memory_pool.h =================================================================== --- tests/zombies/gc_no_raii/src/internal/memory_pool.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/memory_pool.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,92 @@ +#pragma once + +extern "C" { +#include +#include +#include +} + +#include "tools.h" + +#include "card_table.h" +#include "globals.h" +#include "state.h" + +struct gc_memory_pool +{ + struct memory_pool* mirror; + struct memory_pool* next; + + uint8_t type_code; + + card_table_t* cards; + + uint8_t* end_p; + uint8_t* free_p; + uint8_t start_p[1]; +}; + +void ?{}( gc_memory_pool* this, + size_t size, + gc_memory_pool* next, + gc_memory_pool* mirror, + uint8_t type + ); + +void ^?{}(gc_memory_pool* this); + +struct gc_pool_object_iterator +{ + struct gc_object_header* object; + #ifndef NDEBUG + intptr_t lower_limit; + intptr_t upper_limit; + #endif +}; + + +void ?{}( gc_pool_object_iterator* this, + struct gc_object_header* start_object + #ifndef NDEBUG + , intptr_t pool_start + , intptr_t pool_end + #endif + ); + +void ^?{}( gc_pool_object_iterator* this ); + +bool ?!=?(const gc_pool_object_iterator lhs, const gc_pool_object_iterator rhs); + +gc_pool_object_iterator begin(gc_memory_pool* const this); +gc_pool_object_iterator end(gc_memory_pool* const); + +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); + +static 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* const pool); + +static inline size_t gc_pool_size_used(const gc_memory_pool* pool) +{ + return pool->free_p - pool->start_p; +} + +static inline size_t gc_pool_size_total(const gc_memory_pool* pool) +{ + return pool->end_p - pool->start_p; +} + +static 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* const pool, size_t size, bool zero); + +gc_pool_object_iterator gc_pool_iterator_for(gc_memory_pool* const pool, void* member); Index: tests/zombies/gc_no_raii/src/internal/object_header.c =================================================================== --- tests/zombies/gc_no_raii/src/internal/object_header.c (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/object_header.c (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,110 @@ +#include "object_header.h" + +#include + +#include "collector.h" +#include "globals.h" +#include "gcpointers.h" + +void ctor(gc_object_header* const this, size_t inSize) +{ + #ifndef NDEBUG + this->canary_start = CANARY_VALUE; + #endif + + this->size = inSize; + this->root_chain = NULL; + this->type_chain = NULL; + this->forward = NULL; + this->is_forwarded = false; + + #ifndef NDEBUG + this->canary_end = CANARY_VALUE; + #endif +} + +void copy_ctor(gc_object_header* const this, const gc_object_header* const other) +{ + #ifndef NDEBUG + this->canary_start = CANARY_VALUE; + #endif + + this->size = other->size; + this->root_chain = other->root_chain; + this->type_chain = NULL; + this->forward = NULL; + this->is_forwarded = false; + + #ifndef NDEBUG + this->canary_end = CANARY_VALUE; + #endif + + gcpointer_t* root = this->root_chain; + while(root) + { + check(gc_get_object_ptr( (void*)root->ptr ) == other); + root->ptr = ((intptr_t)this) + sizeof(gc_object_header); + + check(gc_get_object_ptr( (void*)root->ptr ) == this); + root = root->next; + } + + gcpointer_t* type = other->type_chain; + + while(type) + { + check((intptr_t)type < (intptr_t)((intptr_t)other + other->size)); + + size_t offset = (intptr_t)type - (intptr_t)other; + check(offset < this->size); + + gcpointer_t* member_ptr = (gcpointer_t*)( (intptr_t)this + offset ); + + if(!this->type_chain) this->type_chain = member_ptr; + + size_t next_offset = type->next ? (intptr_t)type->next - (intptr_t)other : 0; + check(next_offset < this->size); + + gcpointer_t* next_ptr = type->next ? (gcpointer_t*)((intptr_t)this + next_offset) : NULL; + + member_ptr->ptr = type->ptr; + member_ptr->next = next_ptr; + + type = type->next; + } + + check(is_valid(this)); +} + +#ifndef NDEBUG + bool is_valid(const gc_object_header* const this) + { + check((intptr_t)this->canary_start == (intptr_t)CANARY_VALUE); + check((intptr_t)this->canary_end == (intptr_t)CANARY_VALUE); + + check(this->is_forwarded == ( (intptr_t)this->forward != (intptr_t)NULL)); + + check(this->size < POOL_SIZE_BYTES); + + gcpointer_t* root = this->root_chain; + while(root) + { + checkf(gc_get_object_ptr( (void*)root->ptr ) == this, (const char*)"Expected %lX got %lX\n", gc_get_object_ptr( (void*)root->ptr ), this); + + root = root->next; + } + + gcpointer_t* type = this->type_chain; + while(type) + { + check((intptr_t)type > (intptr_t)this); + check((intptr_t)type < (intptr_t)(((intptr_t)this) + this->size)); + + type = type->next; + } + + return true; + } + #else + #error blarg +#endif Index: tests/zombies/gc_no_raii/src/internal/object_header.h =================================================================== --- tests/zombies/gc_no_raii/src/internal/object_header.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/object_header.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,52 @@ +#pragma once + +#include +#include +#include + +#include "tools.h" + +#ifndef NDEBUG + static void* const CANARY_VALUE = (void*)0xCAFEBABACAFEBABA; +#endif + +struct gcpointer_t; +struct gc_object_header; + +struct gc_object_header +{ + #ifndef NDEBUG + void* canary_start; + #endif + + size_t size; + gcpointer_t* root_chain; + gcpointer_t* type_chain; + gc_object_header* forward; + bool is_forwarded; + + #ifndef NDEBUG + void* canary_end; + #endif +}; + +void ctor(gc_object_header* const this, size_t size); +void copy_ctor(gc_object_header* const this, const gc_object_header* const other); + +static inline gc_object_header* placement_ctor(void* address, size_t size) +{ + gc_object_header* const this = (gc_object_header* const) address; + ctor(this, size); + return this; +} + +static inline gc_object_header* placement_copy_ctor(void* address, const gc_object_header* const other) +{ + gc_object_header* const this = (gc_object_header* const) address; + copy_ctor(this, other); + return this; +} + +#ifndef NDEBUG + bool is_valid(const gc_object_header* const this); +#endif Index: tests/zombies/gc_no_raii/src/internal/state.c =================================================================== --- tests/zombies/gc_no_raii/src/internal/state.c (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/state.c (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,312 @@ +#include "state.h" + +#include + +//general purpouse includes +#include "tools.h" + +//platform abstraction includes +#include "allocate-pool.h" + +//gc internal includes +#include "collector.h" +#include "globals.h" +#include "memory_pool.h" +#include "object_header.h" +#include "tools/worklist.h" + +void gc_state_swap(gc_state *const this); +void gc_state_sweep_roots(gc_state *const this, worklist_t* worklist); +void gc_state_clear(gc_state *const this); +void gc_state_calc_usage(gc_state *const this); + +#ifndef NDEBUG + bool gc_state_roots_match(gc_state *const this); + bool gc_state_no_from_space_ref(gc_state *const this); +#endif + +static gc_state s; + +gc_state* gc_get_state() +{ + if(!s.is_initialized) ctor(&s); + return &s; +} + +void ctor(gc_state *const this) +{ + this->from_code = 0; + this->to_space = NULL; + this->from_space = NULL; + this->total_space = 0; + this->used_space = 0; + ctor(&this->pools_table); + + gc_allocate_pool(this); + + this->is_initialized = true; +} + +void dtor(gc_state *const this) +{ + dtor(&this->pools_table); + this->is_initialized = false; +} + +bool gc_is_in_heap(const gc_state* const this, const void* const address) +{ + gc_memory_pool* target_pool = gc_pool_of(address); + + gc_memory_pool** first = cbegin(&this->pools_table); + gc_memory_pool** last = cend(&this->pools_table); + gc_memory_pool** result = find(first, &last, target_pool); + return result != last && gc_pool_is_from_space(*result); +} + +bool gc_is_in_to_space(const gc_state* const this, const void* const address) +{ + gc_memory_pool* target_pool = gc_pool_of(address); + + gc_memory_pool** first = cbegin(&this->pools_table); + gc_memory_pool** last = cend(&this->pools_table); + gc_memory_pool** result = find(first, &last, target_pool); + return result != last && !gc_pool_is_from_space(*result); +} + +gc_object_header* gc_get_object_for_ref(gc_state* state, void* member) +{ + volatile int stage = 0; + intptr_t target = ((intptr_t)member); + if(!gc_is_in_heap(state, member)) return NULL; + stage++; + + gc_memory_pool* pool = gc_pool_of(member); + stage++; + gc_pool_object_iterator it = gc_pool_iterator_for(pool, member); + stage++; + gc_pool_object_iterator end = end(pool); + stage++; + + while(it != end) + { + gc_object_header* object = *it; + check(object); + check( is_valid(object) ); + { + intptr_t start = ((intptr_t)object); + intptr_t end = ((intptr_t)start + object->size); + if(start < target && end > target) + { + return object; + } + } + stage++; + ++it; + } + + checkf( (int) 0, "is_in_heap() and iterator_for() return inconsistent data"); + abort(); + return NULL; +} + +void* gc_try_allocate(gc_state* const this, size_t size) +{ + gc_memory_pool* pool = this->from_space; + while(pool != (gc_memory_pool*)0) + { + if(gc_pool_size_left(pool) > size) + { + return gc_pool_allocate(pool, size, true); + } + pool = pool->next; + } + + return (void*)0; +} + +void gc_allocate_pool(gc_state *const this) +{ + gc_memory_pool* old_from_space = this->from_space; + gc_memory_pool* old_to_space = this->to_space; + + this->from_space = (gc_memory_pool*)(pal_allocPool(POOL_SIZE_BYTES, 1)); + this->to_space = (gc_memory_pool*)(pal_allocPool(POOL_SIZE_BYTES, 1)); + + this->from_space{ POOL_SIZE_BYTES, old_from_space, this->to_space, this->from_code }; + this->to_space { POOL_SIZE_BYTES, old_to_space, this->from_space, (~this->from_code) & 0x01 }; + + this->total_space += gc_pool_size_used(this->from_space); + + push_back(&this->pools_table, this->from_space); + push_back(&this->pools_table, this->to_space); +} + +void gc_collect(gc_state* const this) +{ + // DEBUG("collecting"); + // DEBUG("previous usage " << this->used_space << " / " << this->total_space); + + worklist_t worklist; + ctor(&worklist); + gc_state_sweep_roots(this, &worklist); + + while(!empty(&worklist)) + { + intptr_t* ref = back(&worklist); + pop_back(&worklist); + gc_process_reference((void**)ref, &worklist); + } + + check(gc_state_roots_match(this)); + check(gc_state_no_from_space_ref(this)); + + gc_state_swap(this); + + gc_state_calc_usage(this); + + if(gc_needs_collect(this)) gc_allocate_pool(this); + + // DEBUG("done"); + dtor(&worklist); +} + +void gc_state_swap(gc_state* const this) +{ + swap(&this->from_space, &this->to_space); + + gc_memory_pool* pool = this->to_space; + while(pool) + { + gc_reset_pool(pool); + pool = pool->next; + } + + this->from_code = (~this->from_code) & 0x01; + + #ifndef NDEBUG + { + gc_memory_pool* pool = this->from_space; + while(pool) + { + check(gc_pool_is_from_space(pool)); + pool = pool->next; + } + + pool = this->to_space; + while(pool) + { + check(!gc_pool_is_from_space(pool)); + pool = pool->next; + } + } + #endif +} + +void gc_state_sweep_roots(gc_state* const this, worklist_t* worklist) +{ + gc_memory_pool* pool = this->from_space; + while(pool) + { + gc_pool_object_iterator it = begin(pool); + gc_pool_object_iterator end = end(pool); + for(;it != end; ++it) + { + gc_object_header* object = *it; + if(!object->root_chain) continue; + + gc_copy_object(object); + + gc_scan_object(object->forward, worklist); + } + + pool = pool->next; + } +} + +void gc_state_clear(gc_state* const this) +{ + gc_memory_pool* pool = this->from_space; + while(pool) + { + gc_reset_pool(pool); + pool = pool->next; + } + + pool = this->to_space; + while(pool) + { + gc_reset_pool(pool); + pool = pool->next; + } +} + +void gc_state_calc_usage(gc_state* const this) +{ + this->total_space = 0; + this->used_space = 0; + + gc_memory_pool* pool = this->from_space; + while(pool) + { + size_t size = gc_pool_size_total(pool); + size_t used = gc_pool_size_used(pool); + check(used <= size); + this->total_space += size; + this->used_space += used; + + pool = pool->next; + } +} + +#ifndef NDEBUG + bool gc_state_roots_match(gc_state* const this) + { + gc_memory_pool* pool = this->to_space; + while(pool) + { + size_t size = 0; + gc_pool_object_iterator it = begin(pool); + gc_pool_object_iterator end = end(pool); + for(;it != end; ++it) + { + gc_object_header* object = *it; + size += object->size; + + gcpointer_t* ptr = object->root_chain; + while(ptr) + { + check(gc_get_object_ptr( (void*)ptr->ptr ) == object); + ptr = ptr->next; + } + } + + checkf(size + gc_pool_size_left(pool) == gc_pool_size_total(pool), + (const char*)"expected %lu + %lu == %lu\n", + (size_t)size, + (size_t)gc_pool_size_left(pool), + (size_t)gc_pool_size_total(pool)); + + pool = pool->next; + } + + return true; + } + + bool gc_state_no_from_space_ref(gc_state* const this) + { + gc_memory_pool* pool = this->to_space; + while(pool) + { + void** potential_ref = (void**)pool->start_p; + while(potential_ref < (void**)pool->free_p) + { + check(!gc_is_in_heap(this, *potential_ref)); + potential_ref++; + } + + pool = pool->next; + } + + return true; + } +#endif Index: tests/zombies/gc_no_raii/src/internal/state.h =================================================================== --- tests/zombies/gc_no_raii/src/internal/state.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) +++ tests/zombies/gc_no_raii/src/internal/state.h (revision 87b93323c11d412259391b6741a7bc4dcad8981e) @@ -0,0 +1,64 @@ +#pragma once + +#ifdef __cforall +extern "C" { +#endif +#include +#include +#ifdef __cforall +} +#endif +#include +#include + +#include "tools.h" + +typedef vector(struct gc_memory_pool*, heap_allocator(struct gc_memory_pool*)) pools_table_t; + +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; + + pools_table_t pools_table; + size_t pools_table_count; +}; + +void ctor(gc_state* const state); + +void dtor(gc_state* const state); + +gc_state* gc_get_state(); + +static inline bool gc_needs_collect(gc_state* state) +{ + // sout | "Used Space: " | state->used_space | " bytes"; + return state->used_space * 2 > state->total_space; +} + +void gc_collect(gc_state* const this); + +void* gc_try_allocate(gc_state* const this, size_t size); + +void gc_allocate_pool(gc_state* const state); + +bool gc_is_in_heap(const gc_state* const state, const void* const address); + +bool gc_is_in_to_space(const gc_state* const state, const void* const address); + +static inline uint8_t gc_from_space_code(const gc_state *const this) +{ + return this->from_code; +} + +struct gc_object_header* gc_get_object_for_ref(gc_state* state, void*); + +static inline void gc_register_allocation(gc_state* state, size_t size) +{ + state->used_space += size; +}