Thread-Safe Memory Manager

I developed a simple memory manager further outside of class into a thread-safe memory manager that I now use in my multithreaded engine which supports Quake III BSP loading and a custom Character Animation System.

The primary motivation for the memory manager is to control the allocation of memory to increase locality of references. The memory manager allocates a large block of memory which is then used for all the engine’s memory allocations for increased spatial locality. The engine features recycled object pools within various components to increase temporal locality. Separate threads are used for resource buffering and rendering which perform all heap allocations through the memory manager. In addition, memory usage statistics are tracked and leaks are reported to Visual Studio’s output window.

Source Code

/*
file    MemoryPool.h
date    11/20/2012
author  Warsam Osman
brief   Memory Pool - Thread-Safe Memory Manager - overrides global new/delete
        Tracks memory use statistics and leaks in separate memory.
*/
#pragma once

#ifndef _MEMORY_POOL_
#define _MEMORY_POOL_

#include 
#include "Mutex.h"

namespace core
{
    class MemoryPool;

    /* Templated Thread Safe MemoryPool
    Uses Lock_Type Mutex to make the Pool_Type shared Memory pool thread safe */
    template< class Pool_Type, class Lock_Type >
    class MTMemoryPool 
    {
    public:
        // Passes filename and linenumber to sharedPool for allocation tracking and statistics
        inline void* MTPoolNew( size_t sizeInBytes, char* fileName,  int const lineNumber );
        inline void MTPoolDelete( void* memAddress );

    private:
        Pool_Type sharedPool; 
        Lock_Type lock;
    };

    // Template implementation
    template< class Pool_Type, class Lock_Type >
    inline void* MTMemoryPool< Pool_Type, Lock_Type >::MTPoolNew( size_t sizeInBytes, char* fileName,  int const lineNumber  )
    {
        void* mem = nullptr;
        lock.Lock();
        mem = sharedPool.PoolNew( sizeInBytes, fileName, lineNumber );
        lock.Unlock();
        return mem;
    }

    template< class Pool_Type, class Lock_Type >
    inline void MTMemoryPool< Pool_Type, Lock_Type >::MTPoolDelete( void* memAddress )
    {
        lock.Lock();
        sharedPool.PoolDelete(memAddress);
        lock.Unlock();
    }

    typedef MTMemoryPool< MemoryPool, Mutex > ThreadSafePool;

    extern ThreadSafePool* const GetMemoryPool();
    
    typedef unsigned char Byte;
    typedef size_t BoundaryTag;


// tag size and double tag size 
#define TAGSIZE     4
#define DTAGSIZE    8

    // Memory pool managed with boundary tags & tracks stats / reports leaks
    class MemoryPool
    {
    public:
        MemoryPool();
        ~MemoryPool();  

        // Initialize total memory pool by allocating a large chunk using calloc to 0 out the memory.
        void            Init( size_t sizeBytes );

        /* Called by overridden new to request allocation of sizeInBytes bytes 
        In addition to passing the filename and linenumber when available.
        Otherwise fileName is marked as "unknown" */
        void*           PoolNew( const size_t sizeInBytes, char* fileName,  int const lineNumber  );

        /* Called by overridden delete to deallocate the memory at specified pMemAddress
        The address is checked to verify it is in the pool, otherwise an exception occurs. */
        void            PoolDelete( void* pMemAddress );

        // Returns total space available in bytes
        size_t          SpaceAvailable();

    private:
        // Inline private helpers 

        /* Performs allocation of heap memory by allocation requested size and padding with alignment + overhead.
        Returns nullptr on failure. */
        void*           Alloc( size_t requestSizeBytes );

        // Deallocates allocated memory from passed address and coalesces freed memory using boundary tags.
        void            Dealloc( void* someElement );

        // Uses next fit algorithm to return the first available memory chunk that is big enough. 
        void*           FindFit( size_t sizeBytes );
        
        // Splits the block found by FindFit if bigger than threshold (16 bytes) and updates boundary tags accordingly.
        void            PlaceBlock( void* block, size_t sizeBytes );
        
        // Coalesces blocks of memory using boundary tags.
        void*           Coalesce( void* block );

        // Sets the last bit on the BoundaryTag to indicate whether or not the block is allocated.
        BoundaryTag     SetTagAlloc( size_t size, size_t alloc)     { return size | alloc; }   

        // Gets the BoundaryTag from a passed in address.     
        BoundaryTag&    GetTag( Byte* address )                     { return *(BoundaryTag *)(address); }
        
        // Sets the passed in BoundaryTag to the specified address.            
        void            PutTag( Byte* address, BoundaryTag tag)     { *(BoundaryTag *)(address) = tag; }   

        // Retrieves the block size in bytes from the boundary tag by checking all but the last 3 bits.
        size_t          GetBlockSize( Byte* address )               { return GetTag(address) & ~0x7; } 

        // Checks the allocated bit of BoundaryTag to indicate whether or not the block is allocated.                  
        size_t          BlockAllocated( Byte* address )             { return GetTag(address) & 0x1; }   

        // Get the header BoundaryTag from a passed in block address.
        Byte*           GetHeader( void* block )    { return (Byte*)(block) - TAGSIZE; }   

        // Get the footer BoundaryTag from a passed in block address.	                   
        Byte*           GetFooter( void* block )    { return (Byte*)(block) + GetBlockSize(GetHeader(block)) - DTAGSIZE; }      
        
        // Use the BoundaryTag to get the next memory block
        Byte*           NextBlock( void* block )    { return (Byte*)(block) + GetBlockSize(((Byte*)(block) - TAGSIZE)); } 
        
        // Use the BoundaryTag to get the previous memory block
        Byte*           PrevBlock( void* block )    { return (Byte*)(block) - GetBlockSize(((Byte*)(block) - DTAGSIZE)); } 

        void            ReportStatistics();
        
        // Memory pool 
        Byte*           mem;
        Byte*           current;            
        size_t          poolSize;
        size_t          bytesAlreadyAllocated;

        // Stats
        size_t          totalMemoryPoolSizeInBytes;
        size_t          totalAllocationCount;
        size_t          totalBytesAllocated;
        size_t          largestAllocationBytes;
        size_t          numAllocations;

        // Copy protection
        MemoryPool( MemoryPool& );      
        void operator=( MemoryPool& );  
    };
}

extern core::ThreadSafePool* g_pMemPool;

// Overridden global new and delete variants
void*   operator new( size_t sizeInBytes, char* fileName, int lineNumber ) override;
void    operator delete( void* memAddress ) throw() override;
void    operator delete( void* memAddress, char* fileName, int lineNumber  ) throw() override;
void*   operator new( size_t sizeInBytes ) override;
void*   operator new[]( size_t sizeInBytes ) override;
void    operator delete[]( void* memAddress ) throw() override;
void*   operator new[]( size_t sizeInBytes, char* fileName, int lineNumber ) override;
void    operator delete[]( void* memAddress, char* fileName, int lineNumber  ) throw() override;


#endif //_MEMORY_POOL_
#include "MemoryPool.h"
#include "MallocAllocator.h"
#include 
#include 
#include 
#include 
#include 
#include 
#include 

core::ThreadSafePool* g_pMemPool = nullptr;

namespace core
{
    void OutputDebugFormatStr( const char* str, ... );

    static void _DestroyMemoryPool()
    {
        g_pMemPool->~ThreadSafePool();
        free(g_pMemPool);
        g_pMemPool = nullptr;
    }

    ThreadSafePool* const GetMemoryPool()
    {
        if ( g_pMemPool == nullptr )
        {
            std::atexit(_DestroyMemoryPool);

            g_pMemPool = reinterpret_cast( malloc( sizeof(ThreadSafePool) ) );
            if( g_pMemPool == nullptr )
                throw("Unable to allocate g_pMemPool for MemoryPool");

            g_pMemPool = new (g_pMemPool) ThreadSafePool();
        }

        return g_pMemPool;
    }

    struct CompareAddress
    {
        bool operator() (const void* lhs, const void* rhs) const
        {
            return lhs > > AllocationsMap;
    AllocationsMap* g_allocMap = nullptr;


    //MEMORY POOL //////////////////////////////////////////////////////////
    //
    MemoryPool::MemoryPool()
        :totalMemoryPoolSizeInBytes( 0 )
        ,totalAllocationCount( 0 )
        ,totalBytesAllocated( 0 )
        ,largestAllocationBytes( 0 )
        ,numAllocations( 0 )
    {
        if( g_allocMap == nullptr )
        {
            g_allocMap = reinterpret_cast< AllocationsMap *>( malloc(sizeof(AllocationsMap)) );
            if( g_allocMap == nullptr )
                throw("Unable to allocate g_allocMap for MemoryPool");
            g_allocMap = new (g_allocMap) AllocationsMap();
        }

        Init( MEMORY_POOL_SIZE_BYTES );
    }

    void MemoryPool::Init( size_t sizeBytes )
    {
        poolSize = sizeBytes;

        size_t numWords = poolSize / TAGSIZE;
        size_t adjustedSize = ( numWords%2 ) ? ( numWords+1 ) * TAGSIZE : numWords * TAGSIZE;

        mem = reinterpret_cast< Byte* >( calloc( ( adjustedSize + (3*TAGSIZE)), sizeof(Byte) ) );

        if( mem == nullptr )
            throw("Failed to allocate memory for MemoryPool");

        PutTag(mem, 0);                                         //Alignment padding 
        PutTag(mem + (1*TAGSIZE), SetTagAlloc(DTAGSIZE, 1));    //Prologue header 
        PutTag(mem + (2*TAGSIZE), SetTagAlloc(DTAGSIZE, 1));    //Prologue footer  
        PutTag(mem + (3*TAGSIZE), SetTagAlloc(0, 1));           //Epilogue header 
        mem += (2*TAGSIZE);                     

        current = mem;

        Byte* block = mem;
        PutTag( GetHeader(block), SetTagAlloc( adjustedSize, 0 ));  //Free block header
        PutTag( GetFooter(block), SetTagAlloc( adjustedSize, 0 ));  //Free block footer
        PutTag( GetHeader( NextBlock(block) ), SetTagAlloc(0,1) );  //New epilogue header
    }

    MemoryPool::~MemoryPool()
    {
        //Report any leaks
        if( numAllocations > 0 )
        {
            OutputDebugFormatStr("\nMEMORY LEAKS DETECTED! \n");
            for ( auto it = g_allocMap->begin() ; it != g_allocMap->end(); ++it )
                OutputDebugFormatStr( "%s(%d) not deleted!\n", it->second.m_file, it->second.m_line );
        }

        ReportStatistics();

        g_allocMap->~AllocationsMap();
        free(g_allocMap);
    }

    void* MemoryPool::PoolNew( const size_t sizeInBytes, char* fileName,  int const lineNumber )
    {
        assert( g_allocMap );
        
        void* returnMemAddr = Alloc(sizeInBytes);
        assert( returnMemAddr );

        //Stats 
        totalBytesAllocated += sizeInBytes;
        if( sizeInBytes > largestAllocationBytes )
            largestAllocationBytes = sizeInBytes;
        ++totalAllocationCount;
        ++numAllocations;
        g_allocMap->insert( AllocationsMap::value_type(returnMemAddr,FileLine(fileName,lineNumber)) );

        return returnMemAddr;
    }

    void MemoryPool::PoolDelete( void* pMemAddress )
    {
        assert( g_allocMap );
        assert( pMemAddress );
        auto addrIter = g_allocMap->find( pMemAddress );
        if( addrIter != g_allocMap->end() )
        {
            g_allocMap->erase( addrIter );
            --numAllocations;
        }
        else
        {
            throw("MemoryPool::PoolDelete: address not found!");
            return;
        }
        
        Dealloc(pMemAddress);
    }

    void* MemoryPool::Alloc(size_t requestSizeBytes)
    {
        assert( mem );
        void* foundBlock = nullptr;

        if( requestSizeBytes == 0 ) return nullptr;

        size_t alignedByteSize = ( requestSizeBytes <= DTAGSIZE ) ? 2 * DTAGSIZE : 
            DTAGSIZE * ( (requestSizeBytes + (DTAGSIZE) + (DTAGSIZE-1) ) / DTAGSIZE); //alignment + overhead

        foundBlock = FindFit(alignedByteSize);
        if( foundBlock )
        {
            PlaceBlock( foundBlock, alignedByteSize );
            bytesAlreadyAllocated += alignedByteSize;
            return foundBlock;
        }

        return nullptr;
    }

    void MemoryPool::Dealloc(void *doomed) 
    {
        if( doomed == nullptr ) return;

        size_t sizeInBytes = GetBlockSize( GetHeader(doomed) );

        assert( mem );

        PutTag( GetHeader(doomed), SetTagAlloc(sizeInBytes,0) );
        PutTag( GetFooter(doomed), SetTagAlloc(sizeInBytes,0) );

        Coalesce( doomed );
    }

    void* MemoryPool::FindFit( size_t sizeBytes )
    {
        void* oldCurrent = current;

        //next fit - start at current and search to the end of the list
        for(; GetBlockSize( GetHeader(current) ) > 0; current = NextBlock(current))
        {
            Byte* currentHeader = GetHeader(current);
            assert( currentHeader );
            const size_t currentSizeInHeader = GetBlockSize( currentHeader );
            if( !BlockAllocated( currentHeader ) && (sizeBytes <= currentSizeInHeader ) )
                return current;
        }

        //search from start of list
        for( current = mem; current < oldCurrent; current = NextBlock(current) )
        {
            Byte* currentHeader = GetHeader(current);
            assert( currentHeader );
            const size_t currentSizeInHeader = GetBlockSize( currentHeader );
            if( !BlockAllocated( currentHeader ) && (sizeBytes <= currentSizeInHeader ) )
                return current;
        }

        return nullptr;
    }

    void MemoryPool::PlaceBlock( void* block, size_t sizeInBytes )
    {
        const size_t blockSize = GetBlockSize( GetHeader(block) );

        //Split if enough remaining space
        const size_t remainder = blockSize - sizeInBytes;
        if( remainder >= (2*DTAGSIZE) ) 
        {
            PutTag( GetHeader(block), SetTagAlloc(sizeInBytes,1) );
            PutTag( GetFooter(block), SetTagAlloc(sizeInBytes,1) );
            block = NextBlock( block );
            PutTag( GetHeader(block), SetTagAlloc(remainder, 0) );
            PutTag( GetFooter(block), SetTagAlloc(remainder, 0) );
        }
        else
        {
            PutTag( GetHeader(block), SetTagAlloc(blockSize,1) );
            PutTag( GetFooter(block), SetTagAlloc(blockSize,1) );
        }
    }

    void* MemoryPool::Coalesce( void* block )
    {
        size_t prevAllocated = BlockAllocated( GetFooter( PrevBlock(block) ) );
        size_t nextAllocated = BlockAllocated( GetHeader( NextBlock(block) ) );
        size_t blockSize = GetBlockSize( GetHeader(block) );

        if( prevAllocated && nextAllocated )    
        {
            return block;
        }
        else if( prevAllocated && !nextAllocated ) 
        {
            blockSize += GetBlockSize( GetHeader( NextBlock(block) ) );
            PutTag( GetHeader(block), SetTagAlloc(blockSize, 0) );
            PutTag( GetFooter(block), SetTagAlloc(blockSize, 0) );
        }
        else if( !prevAllocated && nextAllocated )
        {
            blockSize += GetBlockSize( GetHeader( PrevBlock(block) ) );
            PutTag( GetFooter(block), SetTagAlloc(blockSize, 0) );
            PutTag( GetHeader( PrevBlock(block) ), SetTagAlloc(blockSize, 0) );
            block = PrevBlock(block);
        }
        else
        {
            blockSize += GetBlockSize( GetHeader( PrevBlock(block) ) )  +
                GetBlockSize( GetFooter( NextBlock(block) ) );
            PutTag( GetHeader( PrevBlock(block) ), SetTagAlloc(blockSize, 0) );
            PutTag( GetFooter( NextBlock(block) ), SetTagAlloc(blockSize, 0) );
            block = PrevBlock(block);
        }

        if( (current > (Byte*)block) && (current < NextBlock(block) ) )
            current = (Byte*)block;

        return block;
    }

    void MemoryPool::ReportStatistics()
    {
        OutputDebugFormatStr("\n======= MemoryPool Stats (Bytes) ======= \n");
        OutputDebugFormatStr("Total Allocations: %d \n", totalAllocationCount );
        OutputDebugFormatStr("Total Bytes Allocated: %d \n", totalBytesAllocated );
        OutputDebugFormatStr("Largest Allocation Size Bytes Allocated: %d \n", largestAllocationBytes );
        if( totalAllocationCount > 0 )
            OutputDebugFormatStr("Average Allocation Size Bytes Allocated: %g \n", static_cast< float >(totalBytesAllocated / totalAllocationCount ) );
        OutputDebugFormatStr("======= End of Stats ======= \n\n");
    }

    inline void OutputDebugFormatStr( const char* str, ... )
    {
        int len = 0;
        char* buffer = nullptr;
        va_list args;
        va_start(args,str);
        len = _vscprintf( str, args ) + 1; // + '\0'
        if( len > 0 ) buffer = static_cast< char* >( alloca( len* sizeof(char) ) );
        vsprintf_s( buffer, len, str, args );
        OutputDebugStringA( buffer );
    }
}

void* operator new( size_t sizeInBytes, char* fileName, int lineNumber ) 
{
    core::ThreadSafePool* pMemPool = core::GetMemoryPool();
    if( pMemPool == nullptr )
    {
        throw std::bad_alloc();
    }

    return pMemPool->MTPoolNew( sizeInBytes, fileName, lineNumber );
}

void operator delete( void* memAddress ) throw()
{   
    //c++ standard - safe delete null
    if( memAddress == nullptr ) 
        return;

    core::ThreadSafePool* pMemPool = core::GetMemoryPool();

    pMemPool->MTPoolDelete( memAddress );
}

void operator delete( void* memAddress, char*, int ) throw()
{
    delete memAddress;
}

void* operator new( size_t sizeInBytes ) 
{
    return operator new(sizeInBytes,"unknown",-1);
}

void* operator new[]( size_t sizeInBytes ) 
{
    return operator new(sizeInBytes,"unknown",-1);
}

void operator delete[]( void* memAddress ) throw()
{
    delete memAddress;
}

void* operator new[]( size_t sizeInBytes, char* fileName, int lineNumber ) 
{
    return operator new(sizeInBytes, fileName, lineNumber);
}

void operator delete[]( void* memAddress, char*, int ) throw()
{
    delete memAddress;
}

/* 
file    MallocAllocator.h
date    12/18/2012
author  Warsam Osman (based on Stroustrup's The C++ Programming Language source)
brief   Allocator that uses malloc/free instead of new/delete
        useful for containers that we explicitly want to avoid using memory pool 
*/
#pragma  once

#ifndef _MALLOC_ALLOCATOR_
#define _MALLOC_ALLOCATOR_

#include 

namespace core
{
    template < class T >
    class MallocAllocator
    {
    public:
        typedef T value_type;
        typedef size_t size_type;
        typedef ptrdiff_t difference_type;

        typedef T* pointer;
        typedef const T* const_pointer;

        typedef T& reference;
        typedef const T& const_reference;

        pointer address(reference r) const { return &r; }
        const_pointer address(const_reference r) const { return &r; }

        MallocAllocator() throw() {}
        template
        MallocAllocator( const MallocAllocator& ) throw()  {}
        ~MallocAllocator() throw() {}

        pointer allocate( size_type n, const_pointer hint = 0 ) //space for n Ts
        {
            if (n <= 0)
                n = 0;
            else if ((static_cast(-1) / n) < sizeof(T))
                throw std::bad_alloc();

            // allocate storage for n elements of type T
            return ((T*)::malloc(n * sizeof (T))); 
        }

        void deallocate( pointer p, size_type n ) //deallocate n Ts, don't destroy
        {
            free(p);
        }

        void construct( pointer p, const T& val )   //init *p by val in place
        { 
            new(p) T(val); 
        } 
        
        void destroy( pointer p )   //destroy *p but don't deallocate
        { 
            p->~T(); 
        }   

        size_type max_size() const throw() // estimate maximum array size
        { 
            size_t count = (size_t)(-1) / sizeof(T);
            return (0 < count ? count : 1 );
        }

        template
        struct rebind { typedef MallocAllocatorother; }; //in effect: typedef malloc_alloc other
    };

    template 
    inline  bool operator==(const MallocAllocator&, const MallocAllocator&) throw()
    {   // test for malloc_alloc equality (always true)
        return (true);
    }

    template 
    inline  bool operator!=(const MallocAllocator&, const MallocAllocator&) throw()
    {   // test for malloc_alloc inequality (always false)
        return (false);
    }
}

#endif //_MALLOC_ALLOCATOR_