GARIN R. K. RICHARDS
  • HOME
  • linkedin

CODE

Picture

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.
jQuery UI Accordion - Collapse content

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.
jQuery UI Accordion - Collapse content

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.
jQuery UI Accordion - Collapse content

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



Powered by Create your own unique website with customizable templates.
  • HOME
  • linkedin