Custom Block Allocator w/ Variable Alignment and Guardbanding - C++
A Memory Allocator that manages, allocates, and frees memory. Features garbage collection, alignment, and guardbanding in debug builds.
BlockAllocator.h
// Copyright 2016 - 2017 Garin Richards // All Rights Reserved. #pragma once struct BlockDescriptor { BlockDescriptor * prev; void * base; void * user_ptr; size_t master_size; size_t user_size; #if _DEBUG int debug_id; #endif BlockDescriptor * next; }; #include "MonsterDebug.h" #include <assert.h> #include <inttypes.h> #include <malloc.h> #include <new> #define BAND_VAL 0xFD #define BAND_SIZE 4 #define DEFAULT_ALIGNMENT 4 #define DEFAULT_TOTAL_SIZE 1024*1024*100 // 100mb #define DEFAULT_NUM_DESCRIPTORS 5192 namespace Engine { class BlockAllocator { public: BlockAllocator(const size_t i_totalSizeOfAllocator, const unsigned int i_amtOfDescriptors, const uint8_t i_align); ~BlockAllocator(); void * Alloc(const size_t i_amt); void * Alloc(const size_t i_amt, const uint8_t i_align); bool Free(const void* addr_to_free); void GCollect(); #pragma region singleton methods static void CreateInstance(const size_t i_totalSizeOfAllocator, const unsigned int i_amtOfDescriptors, const uint8_t i_align); static void CreateInstance(); //default using defined sizes static BlockAllocator* GetInstance(); static void DestroyInstance(); #pragma endregion singleton methods size_t total_bytes_left = 0; void PrintList(BlockDescriptor* i_root); //For unit tests bool ContainsAddressInBlock(const void* i_addr); bool IsAllocatedAddress(const void* i_addr); size_t GetLargestFreeBlockSize(); //debug #ifdef _DEBUG void DebugPrintState(); #endif private: //list manipulation void InitializeFreeList(const unsigned int i_amtOfDescriptors); void AddToAllocatedList(BlockDescriptor* i_node); void AddToUnallocatedList(BlockDescriptor* i_node); void AddToFreeList(BlockDescriptor* i_node); //BlockConsolidation void CombineBlocks(BlockDescriptor* i_firstBlock, BlockDescriptor* i_secondBlock); //list management void NullRootReference(BlockDescriptor* i_node); void MoveRootReferencesForward(BlockDescriptor* i_node); //debug Checks bool CheckGuardBands(BlockDescriptor* i_node); bool IsPowerOfTwo(const uint8_t i_toCheck); //Block manipulation BlockDescriptor* SearchForBlock(const void * i_addr, BlockDescriptor* i_root) const; BlockDescriptor* FindSuitableUnallocatedBlock(const size_t i_amt) const; BlockDescriptor* RemoveBlockFromList(const void* i_addr, BlockDescriptor* i_root); BlockDescriptor* StealFromBlock(BlockDescriptor* i_victim, const size_t i_amtToTake, const uint8_t i_align); BlockDescriptor* RemoveBlockFromListByBase(const void* i_addr, BlockDescriptor * i_root); #pragma region AllocatorMemberVars BlockDescriptor* free_root_ = 0; BlockDescriptor* allocated_root_ = 0; BlockDescriptor* unallocated_root_ = 0; BlockDescriptor* front_of_pool_ = 0; //front and back addresses of entire allocator void* front_of_chunk_; void* back_of_chunk_; #pragma endregion AllocatorMemberVars #pragma region Singleton vars static BlockAllocator* singleton_instance_; static void* singleton_instance_addr_; #pragma endregion Singleton }; }
BlockAllocator.cpp
// Copyright 2016 - 2017 Garin Richards // All Rights Reserved. #include "BlockAllocator.h" using namespace Engine; //singleton BlockAllocator* BlockAllocator::singleton_instance_ = NULL; void* BlockAllocator::singleton_instance_addr_ = NULL; BlockAllocator::BlockAllocator(const size_t i_totalSizeOfAllocator, const unsigned int i_amtOfDescriptors, const uint8_t i_align) { front_of_chunk_ = _aligned_malloc(i_totalSizeOfAllocator, i_align); assert(front_of_chunk_ != NULL && "Null Memory Allocation in Allocator Creation"); total_bytes_left = i_totalSizeOfAllocator; back_of_chunk_ = reinterpret_cast<uint8_t*>(front_of_chunk_) + i_totalSizeOfAllocator; InitializeFreeList(i_amtOfDescriptors); DEBUGLOG("GALLOCATOR INIT"); PRINT_GALLOC_STATE; } BlockAllocator::~BlockAllocator() { if (allocated_root_ != NULL) { DEBUGLOG("OUTSANDING ALLOCATIONS DETECTED IN BLOCK ALLOCATOR\n"); } _aligned_free(front_of_chunk_); } void* BlockAllocator::Alloc(const size_t i_amt) { return Alloc(i_amt, 4); } void* BlockAllocator::Alloc(const size_t i_amt, const uint8_t i_align) { assert(IsPowerOfTwo(i_align)); if (!IsPowerOfTwo(i_align)) return nullptr; //check to see if we need to garbage collect some nodes if (free_root_ == NULL) { GCollect(); } if (free_root_ == NULL) return nullptr; BlockDescriptor * sufficiently_sized_block = FindSuitableUnallocatedBlock(i_amt); //even after garbage collecting we don't have a descriptor if (sufficiently_sized_block == NULL) return nullptr; //create a new block from block BlockDescriptor * new_descriptor = StealFromBlock(sufficiently_sized_block,i_amt,i_align); //set to requested size new_descriptor->user_size = i_amt; //add to allocated AddToAllocatedList(new_descriptor); DEBUGLOG("User requested %zu BYTES", i_amt); PRINT_GALLOC_STATE; return new_descriptor->user_ptr; } bool BlockAllocator::Free(const void * i_addr) { BlockDescriptor * to_move_to_unallocated = RemoveBlockFromList(i_addr, allocated_root_); assert(to_move_to_unallocated != NULL && "attempted to free a non valid address"); if (to_move_to_unallocated == NULL) { return false; } bool band_integrity_check = CheckGuardBands(to_move_to_unallocated); assert(band_integrity_check && "Guardband corruption"); AddToUnallocatedList(to_move_to_unallocated); DEBUGLOG("User freed addr %04X ", i_addr); PRINT_GALLOC_STATE; return true; } void BlockAllocator::GCollect() { //looking through the list of unallocated blocks, combining any //that are right next to one another, into a single larger //free block BlockDescriptor * conductor = unallocated_root_; //there are no unallocated blocks to look through if (unallocated_root_ == 0) return; while (conductor != NULL) { uint8_t* addr_to_search_for = static_cast<uint8_t*>(conductor->base) + conductor->master_size; BlockDescriptor * found_block = SearchForBlock(addr_to_search_for, unallocated_root_); //if it found nothing, or it's trying to combine itself, move right on. if (found_block == NULL || found_block->base == conductor->base) { conductor = conductor->next; } else { DEBUGLOG("Combining blocks %d and %d\n", conductor->debug_id, found_block->debug_id); CombineBlocks(found_block, conductor); PRINT_GALLOC_STATE; } } DEBUGLOG("AFTER GARBAGE COLLECTION"); PRINT_GALLOC_STATE; } #pragma region Singleton Methods void BlockAllocator::CreateInstance(const size_t i_totalSizeOfAllocator, const unsigned int i_amtOfDescriptors, const uint8_t i_align) { BlockAllocator::singleton_instance_addr_ = _aligned_malloc(sizeof(BlockAllocator), 4); singleton_instance_ = new (singleton_instance_addr_) BlockAllocator(i_totalSizeOfAllocator, i_amtOfDescriptors, i_align); } void BlockAllocator::CreateInstance() { BlockAllocator::singleton_instance_addr_ = _aligned_malloc(sizeof(BlockAllocator), 4); singleton_instance_ = new (singleton_instance_addr_) BlockAllocator(DEFAULT_TOTAL_SIZE, DEFAULT_NUM_DESCRIPTORS, DEFAULT_ALIGNMENT); } BlockAllocator * BlockAllocator::GetInstance() { if (!singleton_instance_) { CreateInstance(DEFAULT_TOTAL_SIZE, DEFAULT_NUM_DESCRIPTORS, DEFAULT_ALIGNMENT); return singleton_instance_; } else { return singleton_instance_; } } void BlockAllocator::DestroyInstance() { singleton_instance_->~BlockAllocator(); _aligned_free(singleton_instance_); singleton_instance_ = NULL; } #pragma endregion Singleton Methods void BlockAllocator::PrintList(BlockDescriptor * i_root) { BlockDescriptor * conductor = i_root; while (conductor != NULL) { DEBUGLOG("[addr:0x%04x id:%d]: prev:0x%04x\tblockptr:%04x\tUserptr:%04x\tsize:%zu\tnext:0x%04x", conductor, conductor->debug_id, conductor->prev, conductor->base, conductor->user_ptr, conductor->master_size, conductor->next); conductor = conductor->next; } } //////////////// ////PRIVATES //////////////// void BlockAllocator::InitializeFreeList(const unsigned int i_amtOfDescriptors) { front_of_pool_ = reinterpret_cast<BlockDescriptor*>(reinterpret_cast<uint8_t*>(back_of_chunk_) - (sizeof(BlockDescriptor) * i_amtOfDescriptors)); //make sure we didn't create too many descriptors assert(front_of_pool_ > front_of_chunk_ && "Too many descriptors, pool is larger than the total size"); //set up front of pool front_of_pool_->prev = NULL; front_of_pool_->base = NULL; front_of_pool_->user_ptr = NULL; front_of_pool_->master_size = 0; front_of_pool_->user_size = 0; BlockDescriptor * conductor = front_of_pool_; #ifdef _DEBUG conductor->debug_id = 0; #endif for (size_t i = 0; i < i_amtOfDescriptors - 1; i++) { BlockDescriptor * new_descriptor = conductor + 1; assert(new_descriptor < reinterpret_cast<BlockDescriptor*>(back_of_chunk_)); //set links conductor->next = new_descriptor; new_descriptor->prev = conductor; new_descriptor->next = NULL; //set properties new_descriptor->base = NULL; new_descriptor->master_size = 0; new_descriptor->user_ptr = NULL; new_descriptor->user_size = 0; #ifdef _DEBUG new_descriptor->debug_id = static_cast<int>(i) + 1; #endif // _DEBUG conductor = new_descriptor; } //free list properties free_root_ = front_of_pool_; total_bytes_left -= sizeof(BlockDescriptor) * i_amtOfDescriptors; //initial unallocated block BlockDescriptor * init_unalloc_block; //steals the last free block to set itself up init_unalloc_block = free_root_; free_root_ = free_root_->next; //set other block properties init_unalloc_block->prev = NULL; init_unalloc_block->base = front_of_chunk_; init_unalloc_block->master_size = total_bytes_left; init_unalloc_block->next = NULL; init_unalloc_block->user_ptr = NULL; init_unalloc_block->user_size = 0; AddToUnallocatedList(init_unalloc_block); } void BlockAllocator::AddToAllocatedList(BlockDescriptor * i_node) { BlockDescriptor * conductor = allocated_root_; //we are the first if (allocated_root_ == 0) { i_node->prev = NULL; i_node->next = NULL; allocated_root_ = i_node; } else { while (conductor->next != NULL) { conductor = conductor->next; } conductor->next = i_node; i_node->prev = conductor; } } void BlockAllocator::AddToUnallocatedList(BlockDescriptor * i_node) { BlockDescriptor * conductor = unallocated_root_; if (unallocated_root_ == 0) { unallocated_root_ = i_node; unallocated_root_->prev = NULL; unallocated_root_->next = NULL; } else { while (conductor->next != NULL) { conductor = conductor->next; } conductor->next = i_node; i_node->prev = conductor; } } void BlockAllocator::AddToFreeList(BlockDescriptor * i_node) { //explicitly null descriptor i_node->base = NULL; i_node->master_size = NULL; i_node->user_size = NULL; i_node->user_ptr = NULL; i_node->next = NULL; i_node->prev = NULL; if (free_root_ == NULL) { free_root_ = i_node; free_root_->prev = NULL; } else { i_node->next = free_root_; free_root_->prev = i_node; free_root_ = i_node; } } bool BlockAllocator::CheckGuardBands(BlockDescriptor * i_node) { uint8_t* front_band_addr = static_cast<uint8_t*>(i_node->user_ptr) - BAND_SIZE; for (size_t i = 0; i < BAND_SIZE; i++) { if (*(front_band_addr + i) != BAND_VAL) { return false; } } uint8_t * back_band_addr = static_cast<uint8_t*>(i_node->user_ptr) + i_node->user_size; for (size_t i = 0; i < BAND_SIZE; i++) { if (*(front_band_addr + i) != BAND_VAL) { return false; } } return true; } void BlockAllocator::CombineBlocks(BlockDescriptor * i_firstBlock, BlockDescriptor * i_secondBlock) { size_t size_of_combined_blocks = i_firstBlock->master_size + i_secondBlock->master_size; i_secondBlock->master_size = size_of_combined_blocks; //RemoveBlockFromList(i_firstBlock->user_ptr, unallocated_root_); RemoveBlockFromListByBase(i_firstBlock->base, unallocated_root_); AddToFreeList(i_firstBlock); } void BlockAllocator::NullRootReference(BlockDescriptor * i_node) { //what type of root are we? Set the appropriate reference if (i_node == free_root_) { free_root_ = NULL; } else if (i_node == allocated_root_) { allocated_root_ = NULL; } else if (i_node == unallocated_root_) { unallocated_root_ = NULL; } } void BlockAllocator::MoveRootReferencesForward(BlockDescriptor * i_node) { //what type of root are we? Set the appropriate reference if (i_node == free_root_) { free_root_ = i_node->next; } else if (i_node == allocated_root_) { allocated_root_ = i_node->next; } else if (i_node == unallocated_root_) { unallocated_root_ = i_node->next; } } BlockDescriptor* BlockAllocator::SearchForBlock(const void * i_addr, BlockDescriptor * i_root) const { BlockDescriptor * conductor = i_root; while (conductor != NULL) { if (conductor->base == i_addr) { return conductor; } else { conductor = conductor->next; } } return nullptr; } BlockDescriptor* BlockAllocator::FindSuitableUnallocatedBlock(const size_t i_amt) const { BlockDescriptor * conductor = unallocated_root_; size_t toLookFor = i_amt; #ifdef _DEBUG toLookFor += BAND_SIZE * 2; #endif while (conductor != NULL) { if (conductor->master_size >= toLookFor) { return conductor; } else { conductor = conductor->next; } } return NULL; } BlockDescriptor* BlockAllocator::RemoveBlockFromList(const void * i_addr, BlockDescriptor * i_root) { BlockDescriptor * conductor = i_root; while (conductor != NULL) { //found it if (conductor->user_ptr == i_addr) { //head case if (conductor->prev == NULL && conductor->next != NULL) { //move root references forward to next MoveRootReferencesForward(conductor); //modify pointers conductor->next->prev = NULL; conductor->next = NULL; } //middle case else if (conductor->prev != NULL && conductor->next != NULL) { conductor->next->prev = conductor->prev; conductor->prev->next = conductor->next; conductor->prev = NULL; conductor->next = NULL; } //tail case else if (conductor->prev != NULL && conductor->next == NULL) { conductor->prev->next = NULL; conductor->prev = NULL; } //root case else if (conductor->prev == NULL && conductor->next == NULL) { //nullify the appropriate root NullRootReference(conductor); } return conductor; } else { //move on conductor = conductor->next; } } return nullptr; } BlockDescriptor* BlockAllocator::StealFromBlock(BlockDescriptor * i_victim, const size_t i_amt, const uint8_t i_align) { //grab a descriptor from the free list BlockDescriptor * thief = free_root_; free_root_ = free_root_->next; //thief doesn't point anywhere, zero out references thief->prev = NULL; thief->next = NULL; size_t entire_amt_to_take = i_amt; #ifdef _DEBUG entire_amt_to_take += BAND_SIZE * 2; #endif //take the front of the victim's space thief->base = i_victim->base; //guardbands #ifdef _DEBUG //check to see if "user ptr" address is aligned void * addr_to_check = static_cast<uint8_t*>(thief->base) + BAND_SIZE; uint8_t * front_guardband_pos; if (reinterpret_cast<size_t>(addr_to_check) % i_align == 0) { //aligned front_guardband_pos = static_cast<uint8_t*>(thief->base); } else { //get padding size_t alignment_padding = i_align - (reinterpret_cast<size_t>(addr_to_check) % i_align); front_guardband_pos = static_cast<uint8_t*>(addr_to_check) + alignment_padding - BAND_SIZE; } for (size_t i = 0; i < BAND_SIZE; i++) { *(front_guardband_pos + i) = BAND_VAL; } //reassign user ptr to be in front of the front guardbands thief->user_ptr = front_guardband_pos + BAND_SIZE; uint8_t* back_guardband_pos = static_cast<uint8_t*>(thief->user_ptr) + i_amt; for (size_t i = 0; i < BAND_SIZE; i++) { *(back_guardband_pos + i) = BAND_VAL; } #endif entire_amt_to_take = (static_cast<uint8_t*>(thief->user_ptr) + i_amt) - static_cast<uint8_t*>(thief->base); //add guardbands for size to modify if in debug #ifdef _DEBUG entire_amt_to_take = (back_guardband_pos + BAND_SIZE) - static_cast<uint8_t*>(thief->base); #endif thief->master_size = entire_amt_to_take; i_victim->master_size -= entire_amt_to_take; i_victim->base = static_cast<uint8_t*>(i_victim->base) + thief->master_size; if (i_victim->master_size == 0) { RemoveBlockFromList(i_victim->user_ptr, unallocated_root_); AddToFreeList(i_victim); } return thief; } BlockDescriptor* BlockAllocator::RemoveBlockFromListByBase(const void * i_addr, BlockDescriptor * i_root) { BlockDescriptor * conductor = i_root; while (conductor != NULL) { //found it if (conductor->base == i_addr) { //head case if (conductor->prev == NULL && conductor->next != NULL) { //move root references forward to next MoveRootReferencesForward(conductor); //modify pointers conductor->next->prev = NULL; conductor->next = NULL; } //middle case else if (conductor->prev != NULL && conductor->next != NULL) { conductor->next->prev = conductor->prev; conductor->prev->next = conductor->next; conductor->prev = NULL; conductor->next = NULL; } //tail case else if (conductor->prev != NULL && conductor->next == NULL) { conductor->prev->next = NULL; conductor->prev = NULL; } //root case else if (conductor->prev == NULL && conductor->next == NULL) { //nullify the appropriate root NullRootReference(conductor); } return conductor; } else { //move on conductor = conductor->next; } } return nullptr; } bool BlockAllocator::IsPowerOfTwo(const uint8_t i_toCheck) { uint8_t val = (i_toCheck != 0) && !(i_toCheck & (i_toCheck - 1)); if (val == 1) return true; else return false; } bool BlockAllocator::ContainsAddressInBlock(const void* i_addr) { if (i_addr <= back_of_chunk_ && i_addr >= front_of_chunk_){ return true; } else { return false; } } bool BlockAllocator::IsAllocatedAddress(const void* i_addr) { BlockDescriptor * conductor = allocated_root_; while (conductor != NULL) { if (conductor->user_ptr == i_addr) { return true; } else { conductor = conductor->next; } } return false; } size_t BlockAllocator::GetLargestFreeBlockSize() { size_t largest = 0; BlockDescriptor * conductor = unallocated_root_; while (conductor != NULL) { if (conductor->master_size > largest) { largest = conductor->master_size; } else { conductor = conductor->next; } } #ifdef _DEBUG if (largest > 0) { largest -= BAND_SIZE * 2; } #endif return largest; } void BlockAllocator::DebugPrintState() { DEBUGLOG("===ALLOCATOR STATE==="); BlockDescriptor * conductor = free_root_; while (conductor != NULL) { DEBUGLOG("FREE NODE [addr:0x%04x id:%d]: prev:0x%04x\tblockptr:%04x\tUserptr:%04x\tsize:%zu\tnext:0x%04x", conductor, conductor->debug_id, conductor->prev, conductor->base, conductor->user_ptr, conductor->master_size, conductor->next); conductor = conductor->next; } conductor = allocated_root_; while (conductor != NULL) { DEBUGLOG("ALLOC NODE [addr:0x%04x id:%d]: prev:0x%04x\tblockptr:%04x\tUserptr:%04x\tsize:%zu\tnext:0x%04x", conductor, conductor->debug_id, conductor->prev, conductor->base, conductor->user_ptr, conductor->master_size, conductor->next); conductor = conductor->next; } conductor = unallocated_root_; while (conductor != NULL) { DEBUGLOG("UNALLOC NODE [addr:0x%04x id:%d]: prev:0x%04x\tblockptr:%04x\tUserptr:%04x\tsize:%zu\tnext:0x%04x", conductor, conductor->debug_id, conductor->prev, conductor->base, conductor->user_ptr, conductor->master_size, conductor->next); conductor = conductor->next; } }
Fixed Size Allocator and BitArray - C++
A fixed size Allocator that manages blocks of a given size. A bit array provides the backend for managing allocated, and free blocks of memory.
FixedSizeAllocator.h
// Copyright 2016 - 2017 Garin Richards // All Rights Reserved. #pragma once #include "BitArray.h" #include "BlockAllocator.h" namespace Engine { class FixedSizeAllocator { public: //static instantiation static FixedSizeAllocator* Create(BlockAllocator* i_allocator, size_t i_amt0fBlocks, size_t i_initialBlockSize); FixedSizeAllocator(const size_t i_initSizeOfBlocks, const size_t i_amtOfBlocks, size_t* i_baseOfBlocks, size_t i_totalSize, BlockAllocator* i_allocator, void* i_fsaBase, void* i_fsaBack); ~FixedSizeAllocator(); //utilities void* Alloc(size_t i_amt); bool Free(void* i_addrToCheck); //helper functions for Memory Manager BitArray* GetArray() const { return bit_array_; }; bool ContainedInAllocator(const void * i_addrToCheck) const; private: size_t size_of_blocks_; size_t num_of_blocks_; size_t* base_address_; size_t total_size_of_FSA_; void* front_of_fsa_; void* back_of_fsa_; //reference for bit array allocation and free BlockAllocator* block_allocator_; BitArray* bit_array_; }; }
FixedSizeAllocator.cpp
// Copyright 2016 - 2017 Garin Richards // All Rights Reserved. #include "FixedSizeAllocator.h" using namespace Engine; FixedSizeAllocator::FixedSizeAllocator(const size_t i_initSizeOfBlocks, const size_t i_amtOfBlocks, size_t* i_baseOfBlocks, size_t i_totalSize, BlockAllocator* i_allocator, void* i_fsaBase, void* i_fsaBack) : size_of_blocks_(i_initSizeOfBlocks), num_of_blocks_(i_amtOfBlocks), base_address_(i_baseOfBlocks), total_size_of_FSA_(i_totalSize), front_of_fsa_(i_fsaBase), back_of_fsa_(i_fsaBack), block_allocator_(i_allocator) { //zero out the memory and create bitarray bit_array_ = BitArray::Create(i_amtOfBlocks, i_allocator); memset(base_address_, 0x00, total_size_of_FSA_ - sizeof(FixedSizeAllocator)); } FixedSizeAllocator::~FixedSizeAllocator() { if (!bit_array_->AreAllClear()) { DEBUGLOG("OUTSTANDING ALLOCATIONS IN FIXED SIZE ALLOCATOR"); } //check bit array and destroy it bit_array_->~BitArray(); block_allocator_->Free(bit_array_); } FixedSizeAllocator* FixedSizeAllocator::Create(BlockAllocator* i_allocator, size_t i_amtOfBlocks, size_t i_sizeOfBlock) { size_t amount_of_bytes = i_sizeOfBlock * i_amtOfBlocks + sizeof(FixedSizeAllocator); void* base_of_fsa = i_allocator->Alloc(amount_of_bytes); size_t* blocks_base_address = reinterpret_cast<size_t*>(reinterpret_cast<uintptr_t>(base_of_fsa) + sizeof(FixedSizeAllocator)); void* back_of_fsa = reinterpret_cast<void*>(static_cast<size_t*>(base_of_fsa) + i_sizeOfBlock * i_amtOfBlocks); //using placement new to create fsa, bypassing overridden new return new (base_of_fsa) FixedSizeAllocator(i_sizeOfBlock, i_amtOfBlocks, blocks_base_address, amount_of_bytes, i_allocator, base_of_fsa, back_of_fsa); } void * FixedSizeAllocator::Alloc(size_t i_amt) { if (i_amt > size_of_blocks_) return nullptr; size_t free_block_check = -1; //ran out of blocks if (bit_array_->AreAllSet()) { DEBUGLOG("RAN OUT OF BLOCKS IN %ud FSA", i_amt); return nullptr; } //get first block that is free size_t free_block = 0; bit_array_->GetFirstClearBit(free_block); uint8_t * addr_for_user = reinterpret_cast<uint8_t*>(base_address_) +(free_block * size_of_blocks_); bit_array_->SetBit(free_block); return static_cast<void*>(addr_for_user); } bool FixedSizeAllocator::Free(void * i_addrToCheck) { //is it even in here? just in case... if (!FixedSizeAllocator::ContainedInAllocator(i_addrToCheck)) { return false; } //cant free if there's nothing to free if (bit_array_->AreAllClear()) { return false; } //which block should we free? size_t block_to_free = static_cast<size_t>(reinterpret_cast<uint8_t*>(i_addrToCheck) - reinterpret_cast<uint8_t*>(base_address_)) / size_of_blocks_; //double free check assert(bit_array_->IsSet(block_to_free)); if (bit_array_->IsClear(block_to_free)) { return false; } //free the block bit_array_->ClearBit(block_to_free); return true; } bool FixedSizeAllocator::ContainedInAllocator(const void * i_addrToCheck) const { uint8_t* back_of_chunk = reinterpret_cast<uint8_t*>(base_address_) + total_size_of_FSA_; //AWW YEAH TERNARY OPERATORS return (i_addrToCheck <= back_of_chunk && i_addrToCheck >= base_address_) ? true : false; }
BitArray.h
// Copyright 2016 - 2017 Garin Richards // All Rights Reserved. #pragma once #include <intrin.h> #include <new> #include <string.h> #include "BlockAllocator.h" #include "MonsterDebug.h" #pragma intrinsic(_BitScanForward) #if _WIN64 typedef uint64_t bitContainer; #define BITSCAN(index_found,value_to_search) _BitScanForward64(index_found,value_to_search) #else typedef uint32_t bitContainer; #define BITSCAN(index_found,value_to_search) _BitScanForward(index_found,value_to_search) #endif namespace Engine { class BitArray { public: //static creation static BitArray * Create(const size_t num_of_bits, Engine::BlockAllocator * my_allocator); ~BitArray(); void ClearAll(); void SetAll(); bool AreAllClear() const; bool AreAllSet() const; bool IsSet(size_t bit_number) const; bool IsClear(size_t bit_number) const; void SetBit(const size_t bit_to_set); void ClearBit(const size_t bit_to_clear); bool GetFirstClearBit(size_t & o_index) const; bool GetFirstSetBit(size_t & o_index) const; inline bool operator[](const size_t index); private: BitArray(const size_t amt_of_user_requested_bits, size_t amt_of_bytes, size_t amt_of_containers, size_t* bits_array_addr); size_t number_of_bits_; size_t number_of_bytes; size_t number_of_containers; size_t* bits_; const size_t bits_per_byte = 8; #ifdef _WIN64 uint64_t BIT_CHECK = 1; #else uint32_t BIT_CHECK = 1; #endif }; }
BitArray.cpp
// Copyright 2016 - 2017 Garin Richards // All Rights Reserved. #include "BitArray.h" using namespace Engine; BitArray * BitArray::Create(const size_t num_of_bits, BlockAllocator * my_allocator) { //Don't forget! const size_t bits_per_byte = 8; //given the amount of bits needed, how many containers will we be needing? 32 - 64 dependent const size_t amt_per_container = bits_per_byte * sizeof(bitContainer); //now, how many containers are we gonna need to store the amount of bits that you need? size_t number_of_containers = (num_of_bits + (amt_per_container - 1)) / amt_per_container; //how much memory we gonna need for all these containers and the bit array structure itself? size_t total_bytes_needed = number_of_containers * sizeof(bitContainer) + sizeof(BitArray); //let's get dat memory void * memory_chunk = my_allocator->Alloc(total_bytes_needed); //but wait, where are the actual bits gonna be? Past the BitArray! size_t* bits_memory = reinterpret_cast<size_t*>(reinterpret_cast<uintptr_t>(memory_chunk) + sizeof(BitArray)); //create dat bit array. return new (memory_chunk) BitArray(num_of_bits, total_bytes_needed, number_of_containers, bits_memory); } BitArray::~BitArray() { //NOTE: Outstanding allocations check and freeing of //BitArray memory is found within the FSA Destructor //FixedSizeAllocator::~FixedSizeAllocator() } void BitArray::ClearAll() { memset(bits_, 0x00, number_of_bytes - sizeof(BitArray)); } void BitArray::SetAll() { memset(bits_, 0xFF, number_of_bytes - sizeof(BitArray)); } bool BitArray::AreAllClear() const { //using bitscanforward, look through all the containers for (size_t i = 0; i < number_of_containers; i++) { unsigned long index = 0; //position of container if (BITSCAN(&index, bits_[i])) { return false; } } return true; } bool BitArray::AreAllSet() const { //using bitscanforward, look through all the containers for (size_t i = 0; i < number_of_containers; i++) { unsigned long index = 0; //position of container if (!BITSCAN(&index,bits_[i])) { return false; } } return true; } bool BitArray::IsSet(size_t bit_number) const { //bit position within the container size_t bit_pos = bit_number % (sizeof(bitContainer) * bits_per_byte); //which container? size_t which_container = bit_number / (sizeof(bitContainer) * bits_per_byte); size_t val = bits_[which_container] & (BIT_CHECK << bit_pos); //OH BOY ANOTHER ONE return (val) ? true : false; } bool BitArray::IsClear(size_t bit_number) const { //bit position within the container size_t bit_pos = bit_number % (sizeof(bitContainer) * bits_per_byte); size_t which_container = bit_number / (sizeof(bitContainer) * bits_per_byte); //which container? size_t val = (*(bits_ + which_container) >> bit_pos) & 1; //AND ANOTHER ONE return (val) ? false : true; } void BitArray::SetBit(const size_t bit_to_set) { size_t bit_pos = bit_to_set % (sizeof(bitContainer)*bits_per_byte); size_t which_container = bit_to_set / (sizeof(bitContainer)*bits_per_byte); *(bits_ + which_container) |= BIT_CHECK << bit_pos; } void BitArray::ClearBit(const size_t bit_to_clear) { size_t bit_pos = bit_to_clear % (sizeof(bitContainer)*bits_per_byte); size_t which_container = bit_to_clear / (sizeof(bitContainer)*bits_per_byte); *(bits_ + which_container) &= ~(BIT_CHECK << bit_to_clear); } bool BitArray::GetFirstClearBit(size_t & o_index) const { size_t bit_pos = 0; size_t bits_left = 0; //negate and use the inverse to find the first set for (size_t i = 0; i < number_of_containers; i++) { unsigned long index = 0; if (i == number_of_containers - 1) { bits_left = number_of_bits_ % (sizeof(bitContainer) * bits_per_byte); if (bits_left == 0) { bits_left = sizeof(bitContainer) * bits_per_byte; } size_t index = 0; while (index < bits_left) { bit_pos = index + (sizeof(bitContainer) * bits_per_byte) * i; if (IsClear(bit_pos)) { o_index = bit_pos; return true; } index++; } } else { //position of container if (BITSCAN(&index, ~bits_[i])) { o_index = (index + (sizeof(bitContainer) * bits_per_byte) * i); return true; } } }//for return false; } bool BitArray::GetFirstSetBit(size_t & o_index) const { size_t bit_pos = 0; size_t bits_left = 0; //using bitscanforward, look through all the containers for (size_t i = 0; i < number_of_containers; i++) { unsigned long index = 0; if (i == number_of_containers - 1) { bits_left = number_of_bits_ % (sizeof(bitContainer) * bits_per_byte); if (bits_left == 0) { bits_left = sizeof(bitContainer) * bits_per_byte; } size_t index = 0; while (index < bits_left) { bit_pos = index + (sizeof(bitContainer) * bits_per_byte) * i; if (IsSet(bit_pos)) { o_index = bit_pos; return true; } index++; } } else { //position of container if (BITSCAN(&index, bits_[i])) { o_index = static_cast<size_t>(index + (sizeof(bitContainer) * bits_per_byte) * i); return true; } } } return false; } inline bool BitArray::operator[](const size_t index) { return IsSet(index); } BitArray::BitArray(const size_t amt_of_user_requested_bits, size_t amt_of_bytes, size_t amt_of_containers, size_t* bits_array_addr) : number_of_bits_(amt_of_user_requested_bits), number_of_bytes(amt_of_bytes), number_of_containers(amt_of_containers), bits_(bits_array_addr) { DEBUGLOG("BitArray created for %zu bits\t%zu containers\t%zu bytes ", amt_of_user_requested_bits,amt_of_containers, amt_of_bytes); //lets set all da containers to empty. memset(bits_, 0x00, amt_of_bytes - sizeof(BitArray)); }
Memory Management System
Using custom block and fixed size allocators, overrides the new and delete operators for memory allocation in a given system.
MemoryManager.h
// Copyright 2016 - 2017 Garin Richards // All Rights Reserved. #pragma once #include "BlockAllocator.h" #include "FixedSizeAllocator.h" #include "MonsterDebug.h" #include <inttypes.h> #define DEFAULT_BLOCK_ALLOCATOR_SIZE 1024*1024*50 #define DEFAULT_NUM_OF_DESCRIPTORS 5192 #define DEFAULT_NUM_OF_FSA_BLOCKS 256 #define DEFAULT_BLOCK_ALLOCATOR_ALIGNMENT 4 #define MAX_FSA_ALLOCATION_SIZE 128 #define SIZEOFSIZES sizeof(default_fsa_sizes) / sizeof(size_t) namespace Engine { class MemoryManager { public: MemoryManager(const size_t i_blockAllocatorSize, const unsigned int i_amtOfDescriptors, const uint8_t i_initAlign); ~MemoryManager(); void* Malloc(const size_t i_amt); void* Malloc(const size_t i_amt, uint8_t i_align); bool Free(void* i_addr); void GCollect(); #pragma region singleton static MemoryManager* GetInstance(); static void CreateInstance(const size_t i_blockAllocatorSize, const unsigned int i_amtOfDescriptors, const int8_t i_initAlign); static void CreateInstance(); //default using defined parameters static void DestroyInstance(); #pragma endregion singleton //debug #ifdef _DEBUG void PrintBlockAllocatorState(); #endif private: BlockAllocator* block_allocator_; FixedSizeAllocator* fixed_allocators_[5]; size_t default_fsa_sizes[5] = { 8, 16, 32, 64, 128 }; #pragma region singleton instance static MemoryManager* manager_instance_; static void* singleton_addr_; #pragma endregion singleton instance }; }
MemoryManager.cpp
// Copyright 2016 - 2017 Garin Richards // All Rights Reserved. #include "MemoryManager.h" using namespace Engine; MemoryManager* MemoryManager::manager_instance_ = NULL; void* MemoryManager::singleton_addr_ = NULL; MemoryManager::MemoryManager(const size_t i_blockAllocatorSize, const unsigned int i_amtOfDescriptors, const uint8_t i_initAlign) { //create block allocator Engine::BlockAllocator::CreateInstance(i_blockAllocatorSize, i_amtOfDescriptors, i_initAlign); block_allocator_ = Engine::BlockAllocator::GetInstance(); //create FSAs for (size_t index = 0; index < SIZEOFSIZES; index++) { fixed_allocators_[index] = FixedSizeAllocator::Create(block_allocator_, DEFAULT_NUM_OF_FSA_BLOCKS, default_fsa_sizes[index]); assert(fixed_allocators_[index] != NULL); } } MemoryManager::~MemoryManager() { //destroy FSAs and free them for (size_t index = 0; index < SIZEOFSIZES; index++) { fixed_allocators_[index]->~FixedSizeAllocator(); block_allocator_->Free(fixed_allocators_[index]); } //destroy block allocator BlockAllocator::DestroyInstance(); } void * MemoryManager::Malloc(const size_t i_amt) { void * user_ptr = NULL; //is this amount small enough to fit within our FSAs? if (i_amt <= MAX_FSA_ALLOCATION_SIZE) { //cool, see if there's room in our FSAs for (size_t i = 0; i < SIZEOFSIZES; i++) { //attempt to malloc, will return a valid ptr if there's //availability and it satisfies the size requirement user_ptr = fixed_allocators_[i]->Alloc(i_amt); if (user_ptr) { return user_ptr; } } } //if we didn't get anything from our FSAs, we need to go and grab it from our block allocator //so, just fall out and get it from the block allocator. user_ptr = Malloc(i_amt, 4); return user_ptr; } void * MemoryManager::Malloc(const size_t i_amt, uint8_t i_align) { //just use the block allocator for proper alignment requirement return block_allocator_->Alloc(i_amt, i_align); } bool MemoryManager::Free(void * i_addr) { //first, let's see if this address is within one of our FSAs for (size_t i = 0; i < SIZEOFSIZES; i++) { if (fixed_allocators_[i]->ContainedInAllocator(i_addr)) { return fixed_allocators_[i]->Free(i_addr); } } //if not, it must be in the block allocator return block_allocator_->Free(i_addr); } void MemoryManager::GCollect() { //garbage collect the block allocator; block_allocator_->GCollect(); } #pragma region singleton MemoryManager * MemoryManager::GetInstance() { if (!manager_instance_) { CreateInstance(DEFAULT_BLOCK_ALLOCATOR_SIZE, DEFAULT_NUM_OF_DESCRIPTORS, DEFAULT_ALIGNMENT); } return manager_instance_; } void MemoryManager::CreateInstance(const size_t i_blockAllocatorSize, const unsigned int i_amtOfDescriptors, const int8_t i_initAlign) { MemoryManager::singleton_addr_ = _aligned_malloc(sizeof(MemoryManager), 4); manager_instance_ = new (singleton_addr_) MemoryManager(i_blockAllocatorSize, i_amtOfDescriptors, i_initAlign); } void MemoryManager::CreateInstance() { MemoryManager::singleton_addr_ = _aligned_malloc(sizeof(MemoryManager), 4); manager_instance_ = new (singleton_addr_) MemoryManager(DEFAULT_BLOCK_ALLOCATOR_SIZE, DEFAULT_NUM_OF_DESCRIPTORS, DEFAULT_ALIGNMENT); } void MemoryManager::DestroyInstance() { manager_instance_->~MemoryManager(); _aligned_free(manager_instance_); manager_instance_ = NULL; } #pragma endregion singleton void MemoryManager::PrintBlockAllocatorState() { block_allocator_->DebugPrintState(); }
MonsterEngine.h (Operator Overrides)
// Copyright 2016 - 2017 Garin Richards // All Rights Reserved. #pragma once #include <stdlib.h> #include <time.h> #include "BlockAllocator.h" #include "MemoryManager.h" #include "MonsterDebug.h" void * operator new(size_t n); void * operator new(size_t n, const char * msg); void * operator new(size_t n, const uint8_t alignment); void operator delete(void * p); void operator delete(void * p, const char * msg); void * operator new[](size_t n); void * operator new[](size_t n, const uint8_t alignment); void operator delete[](void * p); void operator delete[](void * p, const char * msg);
MonsterEngine.cpp (Operator Overrides)
// Copyright 2016 - 2017 Garin Richards // All Rights Reserved. #include "MonsterEngine.h" #define DEFAULT_BLOCK_ALLOCATOR_SIZE 1024*1024*50 #define DEFAULT_NUM_OF_DESCRIPTORS 5192 #define DEFAULT_NUM_OF_FSA_BLOCKS 256 #define DEFAULT_BLOCK_ALLOCATOR_ALIGNMENT 4 using namespace Engine; //regular new using our allocator void * operator new(size_t n) { return MemoryManager::GetInstance()->Malloc(n); } //support for debug logs void * operator new(size_t n, const char * msg) { DEBUGLOG(msg); return MemoryManager::GetInstance()->Malloc(n); } void * operator new(size_t n, const uint8_t alignment) { return MemoryManager::GetInstance()->Malloc(n, alignment); } //delete using our allocator void operator delete(void * p) { bool result = MemoryManager::GetInstance()->Free(p); assert(result); } //delete using debug log, will never get called. All funnels down to regular //delete functions void operator delete(void * p, const char * msg) { DEBUGLOG(msg); bool result = MemoryManager::GetInstance()->Free(p); assert(result); } //regular new[] using our allocator void * operator new[](size_t n) { return MemoryManager::GetInstance()->Malloc(n); return nullptr; } void * operator new[](size_t n, const uint8_t alignment) { return MemoryManager::GetInstance()->Malloc(n, alignment); } //delete[] using our allocator void operator delete[](void * p) { bool result = MemoryManager::GetInstance()->Free(p); assert(result); } //delete using debug log, won't get called. void operator delete[](void * p, const char * msg) { DEBUGLOG(msg); bool result = MemoryManager::GetInstance()->Free(p); assert(result); }