Thread: Problem with custom dynamic memory allocation routines

Hi there,

I've written a very basic dynamic memory allocation class which ensures that any dynamically allocated memory is automatically deallocated when the program ends, essentially providing a basic garbage collection feature. The class uses a simple structure to keep track of all the memory that is allocated and again uses this when deallocating memory (either manually or automatically at the program's end). The only problem is that sometimes the tracker will record duplicate entries for the same block of memory, meaning that when a particular block of memory is freed, if the tracker has duplicate entries then it will inevitably try to free the same block of memory twice, thus causing the program to crash. I've tried several things to get around this but cannot work out specifically what is causing the problem. The code I've got is below:

Code:

// memorg.h

struct MEMORYTRACKER
{
    void *MemBlock;             // All-purpose pointer to the block of T objects
    bool Allocated;             // Whether this block has yet been allocated
    unsigned long NumObjects;   // The number of T objects allocated in this block
};

class DLLIMPORT MEMORY
{
public:
    MEMORY();
    ~MEMORY();
    template <typename T> inline T *Allocate(unsigned long);
    template <typename T> inline T *Resize(T *, unsigned long);
    template <typename T> inline void Deallocate(T *);
private:
    MEMORYTRACKER *MT;
    unsigned long NumMemBlocks;
};

template <typename T>
T *MEMORY::Allocate(unsigned long Num)
{
    T *MemBlock, *NewMem;

    NumMemBlocks++;

    MT = (MEMORYTRACKER *) realloc(MT, NumMemBlocks * sizeof(MEMORYTRACKER));
    
    // This ensures that the T objects are constructed properly..
    NewMem = new T[Num];
    
    // ..while this allows us to use realloc later on if need be
    MemBlock = (T *) malloc(Num * sizeof(T));
    
    // We copy the constructed T objects into the space allocated by malloc..
    memcpy(MemBlock, NewMem, Num * sizeof(T));
    
    // ..then delete the temporary memory allocated with new
    delete [] NewMem;
    
    MT[NumMemBlocks - 1].MemBlock = MemBlock;
    MT[NumMemBlocks - 1].Allocated = true;
    MT[NumMemBlocks - 1].NumObjects = Num;
    
    return MemBlock;
}

template <typename T>
T *MEMORY::Resize(T *MemBlock, unsigned long Num)
{
    unsigned long i;
    unsigned long MemBlockNum;
    bool MemBlockFound = false;
    
    for(i = 0; i < NumMemBlocks; i++)
    {
        if(MT[i].MemBlock == MemBlock)
        {
            MemBlockNum = i;
            MemBlockFound = true;
        }
        
        if(MemBlockFound)
        {
            break;
        }
    }
    
    if(MemBlockFound)
    {
        MemBlock = (T *) realloc(MemBlock, Num * sizeof(T));

        if(MT[MemBlockNum].NumObjects < Num)
        {
            // We're resizing the memory block to a larger size than previously, so whatever the
            // size difference is, we use new to allocate the extra T objects so that they will
            // be properly constructed, while the existing data remains unchanged
            unsigned long NumObjects = Num - MT[MemBlockNum].NumObjects;
            
            T *NewMem = new T[NumObjects];
            
            memcpy(MemBlock + MT[MemBlockNum].NumObjects, NewMem, NumObjects * sizeof(T));

            delete [] NewMem;
        }

        MT[MemBlockNum].MemBlock = MemBlock;
        MT[MemBlockNum].Allocated = true;
        MT[MemBlockNum].NumObjects = Num;
    }
    else
    {
        MemBlock = Allocate<T>(Num);
    }
    
    return MemBlock;
}

template <typename T>
void MEMORY::Deallocate(T *MemBlock)
{
    unsigned long i;

    for(i = 0; i < NumMemBlocks; i++)
    {
        if(MT[i].MemBlock == MemBlock && MT[i].Allocated)
        {
            free(MemBlock);
            MT[i].Allocated = false;
        }
    }
}

class DLLIMPORT MemOrg
{
public:
    static MEMORY &GetMemory();
private:
    static MEMORY Mem;
};

//////////////////////////

// memorg.cpp

#include "memorg.h"

MEMORY MemOrg::Mem;

MEMORY::MEMORY()
{
    MT = (MEMORYTRACKER *) malloc(0);
    NumMemBlocks = 0;
}

MEMORY::~MEMORY()
{
    unsigned long i;
    
    for(i = 0; i < NumMemBlocks; i++)
    {
        if(MT[i].Allocated)
        {
            free(MT[i].MemBlock);
        }
    }
    
    free(MT);
}

MEMORY &MemOrg::GetMemory()
{
    return Mem;
}

I've tried re-writing the code so that all dynamic memory allocation is done purely with new and delete, yet the same problem occurs so I know it's nothing to do with that (I have my own reasons for using C-style memory allocation in places so I'm not looking to start a malloc vs new debate or anything like that). I'm sure there's something small that I'm missing here, but I'm at my wits end trying to resolve this situation. If anyone can shed any insight it would be much appreciated.

Kind regards,

BLauritson

Hi anon,

Thanks for the quick reply. I must admit I wasn't aware of the issues surrounding things like memcpy and realloc on the unknown type T. I also have a re-written version of the same code which exclusively uses new and delete (and some extra templates). I'm not sure how many of the problems you identified that this version of the code solves, although I still get the same run-time errors with this one:

Code:

#define Memory(X)    MemOrg<X>::GetMemory()

template <typename T>
struct MEMORYTRACKER
{
    T *MemBlock;                // All-purpose pointer to the block of T objects
    bool Allocated;             // Whether this block has yet been allocated
    unsigned long NumObjects;   // The number of T objects allocated in this block
};

template <typename T>
class DLLIMPORT MEMORY
{
public:
    MEMORY();
    ~MEMORY();
    T *Allocate(unsigned long);
    T *Resize(T *, unsigned long);
    void Deallocate(T *);
private:
    MEMORYTRACKER<T> *MT;
    unsigned long NumMemBlocks;
};

template <typename T>
MEMORY<T>::MEMORY()
{
    MT = new MEMORYTRACKER<T>[0];
    NumMemBlocks = 0;
}

template <typename T>
MEMORY<T>::~MEMORY()
{
    unsigned long i;
    
    for(i = 0; i < NumMemBlocks; i++)
    {
        if(MT[i].Allocated)
        {
            delete [] MT[i].MemBlock;
        }
    }
    
    delete [] MT;
}

template <typename T>
T *MEMORY<T>::Allocate(unsigned long Num)
{
    unsigned long i;
    T *MemBlock, *NewMem;

    NumMemBlocks++;

    MEMORYTRACKER<T> *NewMT = new MEMORYTRACKER<T>[NumMemBlocks];
    
    for(i = 0; i < NumMemBlocks - 1; i++)
    {
        NewMT[i] = MT[i];
    }
    
    delete [] MT;
    
    MT = NewMT;
    
    MemBlock = new T[Num];
    
    MT[NumMemBlocks - 1].MemBlock = MemBlock;
    MT[NumMemBlocks - 1].Allocated = true;
    MT[NumMemBlocks - 1].NumObjects = Num;
    
    return MemBlock;
}

template <typename T>
T *MEMORY<T>::Resize(T *MemBlock, unsigned long Num)
{
    unsigned long i;
    unsigned long MemBlockNum;
    bool MemBlockFound = false;
    
    for(i = 0; i < NumMemBlocks; i++)
    {
        if(MT[i].MemBlock == MemBlock)
        {
            MemBlockNum = i;
            MemBlockFound = true;
        }
        
        if(MemBlockFound)
        {
            break;
        }
    }
    
    if(MemBlockFound)
    {
        T *NewMem = new T[Num];
        
        unsigned long NumObjects = (MT[MemBlockNum].NumObjects < Num) ? MT[MemBlockNum].NumObjects : Num;
        
        for(i = 0; i < NumObjects; i++)
        {
            NewMem[i] = MemBlock[i];
        }
        
        delete [] MemBlock;
        
        MemBlock = NewMem;
        
        MT[MemBlockNum].MemBlock = MemBlock;
        MT[MemBlockNum].Allocated = true;
        MT[MemBlockNum].NumObjects = Num;
    }
    else
    {
        MemBlock = Allocate(Num);
    }
    
    return MemBlock;
}

template <typename T>
void MEMORY<T>::Deallocate(T *MemBlock)
{
    unsigned long i;
    
    for(i = 0; i < NumMemBlocks; i++)
    {
        if(MT[i].MemBlock == MemBlock && MT[i].Allocated)
        {
            delete [] MemBlock;
            
            MT[i].Allocated = false;
        }
}

template <typename T>
class DLLIMPORT MemOrg
{
public:
    static MEMORY<T> &GetMemory();
private:
    static MEMORY<T> Mem;
};

template <typename T>
MEMORY<T> MemOrg<T>::Mem;

template <typename T>
MEMORY<T> &MemOrg<T>::GetMemory()
{
    return Mem;
}

I've (perhaps naively) assumed that calling delete would call the class destructor on an object here - if that's not the case how would I go about doing so?

Kind regards,

BLauritson

OK, I'll have to do that then when I have some more time. Thanks for all your help

BLauritson

If the class dumped a catalog* of some kind for the neglected pointers it could be useful during debugging.

I'm not to sure how it would be useful in the general case.

Soma

Code:

* {typeid(TYPE).name(), Count, __LINE__, __FILE__}

Originally Posted by anon

The point of garbage collection is to ensure that a program doesn't run out of memory while it is running by discarding unused objects as needed and recycling the memory. If I'm not mistaken, when the program finishes, the garbage collector (e.g in C#) will be more than happy to leak all the memory and leave it to the OS to clean up.

I must admit I didn't realise that - for some reason I was under the impression that if a program leaked memory, that memory then remained unavailable to the operating system (even after the program closed) until, say, the computer was shut down and restarted for example. That was the only real reason I even started doing these custom routines, apparently trying to solve a problem that doesn't even exist (at least, not for the sort of program this library would be intended for anyway). I'll do some more research first but based on what you've said it sounds like I may not need to use my custom routines anyway. Oh well, I've still learned some things through doing all of this so even if I do end up discarding it, it won't have been a wasted effort.

Originally Posted by phantomotap

If the class dumped a catalog* of some kind for the neglected pointers it could be useful during debugging.

I'm not to sure how it would be useful in the general case.

Soma

Code:

* {typeid(TYPE).name(), Count, __LINE__, __FILE__}

Thanks for the tip, I'll bear that in mind.

Thanks again for everyone's help with this, it's certainly saved me a lot of stress in the long run

Kind regards,

BLauritson