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);
}
