Problem with custom dynamic memory allocation routines

This is a discussion on Problem with custom dynamic memory allocation routines within the C++ Programming forums, part of the General Programming Boards category; Hi there, I've written a very basic dynamic memory allocation class which ensures that any dynamically allocated memory is automatically ...

  1. #1
    Registered User BLauritson's Avatar
    Join Date
    Mar 2010
    Posts
    5

    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

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
        // 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;
    You can't move an unknown type T with memcpy or realloc. Suppose my class hands out a pointer to itself (e.g so objects can call back to it). When you move the parent around in memory, the children will have no way of knowing their parent is not at the same place any more.

    Basically your strategy here is to have objects that have never been created. Objects have to be created with a constructor. If they are to be copied, this must be done with the copy constructor.

    I didn't study this thing very hard, but I suppose it doesn't even attempt to call destructors when cleaning up? If so it is somewhat of a wasted effort: when the program terminates, the OS cleans up the memory leaks anyway. Memory leaks hurt you while the program is running - does your code help against these leaks?
    Last edited by anon; 03-10-2010 at 01:16 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by anon View Post
    I suppose it doesn't even attempt to call destructors when cleaning up?
    Ouch, major oversight right there. I think it will also be impossible to use with an inherited class than involves stuff in the constructor. So as long as you don't use it for objects it should be fine!

    Another issue is that you need to grab double the amount of memory to initialize, and it will take (at least) twice as long. So while the intention is good, I am pretty sure this is only going to lead to worse memory management and not better.

    Vis, your problem, you should set pointers to NULL 1) before you allocate them, 2) after you free() them, and always test for NULL before you allocate. This will prevent double frees.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Registered User BLauritson's Avatar
    Join Date
    Mar 2010
    Posts
    5
    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

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    This code contains just the classes. Where's the code where you use it and have problems?

    (And just to be sure, you are aware that this problem - managing memory for arrays of objects - is already solved in C++ with the use of std::vector (and boost::ptr_vector and boost::shared_array etc)?)
    Last edited by anon; 03-10-2010 at 01:46 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User BLauritson's Avatar
    Join Date
    Mar 2010
    Posts
    5
    Code:
    SPELLS *AvailableSpells = Memory(SPELLS).Allocate(0);   // Simply set up the pointers
    SPELLS *BestSpells = Memory(SPELLS).Allocate(0);
    
    for(i = 0; i < NumSpellsKnown; i++)
    {
        if(SpellTypesAllowed[Spells[SpellsKnown[i]].SpellType])
        {
            if(NPCs(NPCNum)->GetSP() >= SpellCost(SpellsKnown[i], NPCNum))
            {
                NumSpellsAnalysed++;
                AvailableSpells = Memory(SPELLS).Resize(AvailableSpells, NumSpellsAnalysed);
                AvailableSpells[NumSpellsAnalysed - 1] = SpellsKnown[i];
            }
        }
    }
    
    if(NumSpellsAnalysed > 0)
    {
        unsigned long MaxSpellEffectiveness[NumSpellsAnalysed];
        
        for(i = 0; i < NumSpellsAnalysed; i++)
        {
            /////////////////////////
            // This is where the code crashes
            /////////////////////////
    
            MaxSpellEffectiveness[i] = Spells[AvailableSpells[i]].Mag1 * Spells[AvailableSpells[i]].Mag2 * Spells[AvailableSpells[i]].MPL;
            HighestMaxEffectiveness = max(HighestMaxEffectiveness, MaxSpellEffectiveness[i]);
        }
        
        for(i = 0; i < NumSpellsAnalysed; i++)
        {
            if(MaxSpellEffectiveness[i] == HighestMaxEffectiveness)
            {
                NumBestSpells++;
                BestSpells = Memory(SPELLS).Resize(BestSpells, NumBestSpells);
                BestSpells[NumBestSpells - 1] = AvailableSpells[i];
            }
        }
        
        // Other irrelevant code
    }
    
    Memory(SPELLS).Deallocate(AvailableSpells);
    Memory(SPELLS).Deallocate(BestSpells);
    The "SPELLS" data type is simply an enum.

    Testing revealed that a few elements of the AvailableSpells[] array were becoming corrupted somehow when the array was being resized. Whereas, say for example, Spells[5] would originally be assigned the value 10, once it was resized this value would change to something ridiculous like 104857. This didn't happen to all array elements though.

    EDIT: I am indeed aware that the problem has been solved before. The main reason I'm doing this is it's part of a personal project I'm working on and a lot of the code I'm doing is reinventing the wheel purely so I can learn more about how it all works behind the scenes etc..

    EDIT 2: Sorry, I also forgot to mention that when I was testing this code to find out where the error was occurring, I tried replacing my custom routines simply with malloc, realloc and free for this particular section of code only. When I did this, there were no problems whatsoever, which is what leads me to believe that it's my custom routines which are buggy.
    Last edited by BLauritson; 03-10-2010 at 02:07 PM.

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I think you'll just need to work with a debugger. It is just too hard to debug a fragment of code by just reading it. It may well be that the user code is doing something wrong (e.g accessing arrays out of bounds), and it just happens to "work" with different allocation functions.
    Last edited by anon; 03-10-2010 at 03:44 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Registered User BLauritson's Avatar
    Join Date
    Mar 2010
    Posts
    5
    OK, I'll have to do that then when I have some more time. Thanks for all your help

    BLauritson

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    EDIT: I am indeed aware that the problem has been solved before. The main reason I'm doing this is it's part of a personal project I'm working on and a lot of the code I'm doing is reinventing the wheel purely so I can learn more about how it all works behind the scenes etc..
    Well good luck with it.

    Just making sure you are not reinventing very square wheels: how is forgetting to delete[] an array that you are supposed to manage any different from forgetting to call Deallocate at right places with this class?

    The result is the same: until the program terminates this memory will be lost to it. It doesn't matter if you don't have any pointers to the resource at all or you do have a pointer - which you can't use to release the memory anyway.

    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 might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,260
    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__}

  11. #11
    Registered User BLauritson's Avatar
    Join Date
    Mar 2010
    Posts
    5
    Quote Originally Posted by anon View Post
    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.

    Quote Originally Posted by phantomotap View Post
    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

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    6,299
    Quote Originally Posted by BLauritson View Post
    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.
    Such problems did exist with some older operating systems.

    Modern operating systems are designed to avoid such things - at least in applications executed by users.
    Right 98% of the time, and don't care about the other 3%.

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by BLauritson View Post
    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.
    Yeah, that'd be my $0.02 on this one. Time to start getting comfortable with a debugger too, BLauritson -- sooner or later you'll run into something that can't be solved another way. And don't forget:

    you should set pointers to NULL 1) before you allocate them, 2) after you free() them, and always test for NULL before you allocate. This will prevent double frees.
    It will also help you with (manual) clean up. If you are on linux and concerned you have forgotten some pointers, investigate valgrind, it will give you a quick and simple report of how much memory was (or was not) leaked during execution.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  2. Memory dynamic allocation
    By elvio.vicosa in forum C Programming
    Replies: 8
    Last Post: 10-16-2007, 03:30 AM
  3. pointers
    By InvariantLoop in forum C Programming
    Replies: 13
    Last Post: 02-04-2005, 08:32 AM
  4. Dynamic memory allocation
    By amdeffen in forum C++ Programming
    Replies: 21
    Last Post: 04-29-2004, 08:09 PM
  5. Is it necessary to write a specific memory manager ?
    By Morglum in forum Game Programming
    Replies: 18
    Last Post: 07-01-2002, 01:41 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21