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.

/*
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 <cassert>
#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_

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

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 <cassert>

#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 <cstdlib>
#include <stdio.h>
#include <malloc.h>
#include <stdarg.h>
#include <new>
#include <windows.h>
#include <map>

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<ThreadSafePool*>( 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<rhs;
        }
    };

    struct FileLine
    {
        FileLine( char* fileName, const int lineNumber )
            :m_file( fileName )
            ,m_line( lineNumber )
        {}

        char* m_file;
        int m_line;
    };

    //Map that uses malloc for allocations - too keep stats and leak detection separate from managed memory
    typedef std::map<void*,FileLine,CompareAddress, MallocAllocator< std::pair<void*,FileLine> > > 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;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

#include "MemoryPool.h"

#include "MallocAllocator.h"

#include <cstdlib>

#include <stdio.h>

#include <malloc.h>

#include <stdarg.h>

#include <new>

#include <windows.h>

#include <map>

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<ThreadSafePool*>( 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<rhs;

}

};

struct FileLine

{

FileLine( char* fileName, const int lineNumber )

:m_file( fileName )

,m_line( lineNumber )

{}

char* m_file;

int m_line;

};

//Map that uses malloc for allocations - too keep stats and leak detection separate from managed memory

typedef std::map<void*,FileLine,CompareAddress, MallocAllocator< std::pair<void*,FileLine> > > 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 <cstdlib>

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<class U>
        MallocAllocator( const MallocAllocator<U>& ) 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<size_t>(-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<class U>
        struct rebind { typedef MallocAllocator<U>other; }; //in effect: typedef malloc_alloc<U> other
    };

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

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

#endif //_MALLOC_ALLOCATOR_

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 <cstdlib>

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<class U>

MallocAllocator( const MallocAllocator<U>& ) 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<size_t>(-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<class U>

struct rebind { typedef MallocAllocator<U>other; }; //in effect: typedef malloc_alloc<U> other

};

template<class T>

inline bool operator==(const MallocAllocator<T>&, const MallocAllocator<T>&) throw()

{ // test for malloc_alloc equality (always true)

return (true);

}

template<class T>

inline bool operator!=(const MallocAllocator<T>&, const MallocAllocator<T>&) throw()

{ // test for malloc_alloc inequality (always false)

return (false);

}

#endif //_MALLOC_ALLOCATOR_