Linked List issue / debugging
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Thread: Linked List issue / debugging

  1. #1
    Join Date
    Dec 2010
    Posts
    18

    Question Linked List issue / debugging

    I have been struggling with this problem for about 2 days now and I just cant figure out what the problem is.
    I am making a linked list that points to a char array at different addresses.
    So for the 8byte linked list, it points to an address every 8 bytes.
    link lists 32bytes, 64bytes etc also follow the same pattern.
    Here is the code that is giving me issues:
    Code:
    void CMemoryPoolManager::initializeLinkedList(char MM_pool[], int chunks, int chunkSize, int offset)
      {
    	MemoryBlock current;
    	MemoryBlock *pCurrent = NULL;
            pCurrent = &current;
    	for (int i=0; i < chunks; i++)
    	{
    		pCurrent = (MemoryBlock *)&MM_pool[sizeof(CMemoryPoolManager) +1 + (i * chunkSize) + offset];
    		pCurrent->pNext = NULL;
    		pCurrent->pPrevious = NULL;
    		pCurrent->bInUse = false;
    
    		switch (chunkSize)
    		{
    		case 8:
    			pCurrent->pNext = p8Byte;
    			if (p8Byte != NULL)
    				p8Byte->pPrevious = pCurrent;
    			p8Byte = pCurrent;
    			break;
    		case 32:
    			pCurrent->siSize = 32;
    			pCurrent->pNext = p32Byte;
    			if (p32Byte != NULL)
    				p32Byte->pPrevious = pCurrent;
    			p32Byte = pCurrent;
    			break;
    		case 64:
    			pCurrent->siSize = 64;
    			pCurrent->pNext = p64Byte;
    			if (p64Byte != NULL)
    				p64Byte->pPrevious = pCurrent;
    			p64Byte = pCurrent;
    			break;
    
    		}
    	}
    }
    MemoryBlock is a struct in CMemoryPoolManager that holds the pointers next and previous
    size is just for testing disregard that.
    and the p##Byte are the linked lists inside CMemoryPoolManager
    the line:
    Code:
    pCurrent = (MemoryBlock *)&MM_pool[sizeof(CMemoryPoolManager) +1 + (i * chunkSize) + offset];
    gets the position of where to create the next "node".

    Now on to the question / problem.
    When creating the 8byte list,it doesnt link properly.
    When it hits the "case 8:" line pCurrent->pNext changes by itself and subsequently changes the p8Byte links. So it never creates a proper list.
    What really makes things weird is that the 32 and 64 byte lists are made correctly with no issues. Its the same code, it follows the same pattern, but the 8Byte list just doesnt work for whatever reason!
    I have no clue as to why...ive tried a variety of things and nothing seems to help.
    Can anyone suggest anything to try or see what the issue might be?
    Any help at all would be GREATLY appreciated!!
    Thanks!
    -G

  2. #2
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Linked List issue / debugging

    Quote Originally Posted by ghostfacelz View Post
    I have been struggling with this problem for about 2 days now and I just cant figure out what the problem is.
    Before anything, have you considered just using std::list with a custom allocator? That would have been much easier than trying to code the entire linked list.

    Regards,

    Paul McKenzie

  3. #3
    Join Date
    Dec 2010
    Posts
    18

    Re: Linked List issue / debugging

    Yea, there are a lot of ways I could have done this project that would have made things MUCH easier. Unfortunately there are some constraints.
    no global or static variables
    All saved data needs to be stored inside the memory pool
    No use of new/malloc
    Etc... so std::list couldnt be used.
    Which isn't too big a deal because linked lists are pretty easy to implement.

  4. #4
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Linked List issue / debugging

    Quote Originally Posted by ghostfacelz View Post
    When creating the 8byte list,it doesnt link properly. When it hits the "case 8:" line pCurrent->pNext changes by itself and subsequently changes the p8Byte links. So it never creates a proper list.
    Sounds like memory corruption and/or pointer mismanagement in other parts of your code or how you've used this class.

    You should post a small, complete, but minimal program that demonstrates this error. If you can't do that (you tried, but can't duplicate the error with a small program), then that's more of a reason to suspect it's your larger program that's causing the trouble.

    Regards,

    Paul McKenzie

  5. #5
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Linked List issue / debugging

    Quote Originally Posted by ghostfacelz View Post
    Yea, there are a lot of ways I could have done this project that would have made things MUCH easier. Unfortunately there are some constraints.
    no global or static variables
    All saved data needs to be stored inside the memory pool
    No use of new/malloc
    Etc... so std::list couldnt be used.
    I don't think you understood.

    The std::list class takes a custom allocator. That custom allocator can do exactly what your code is doing now, but without the micromanaging of the list itself. That is the beauty of many of the STL container classes -- you have the option of controlling exactly how memory is "allocated" (it could be new/delete, from your own custom pool, etc.)
    Code:
    std::list<T, allocator>
    That is the full definition of std::list.

    Regards,

    Paul McKenzie

  6. #6
    Join Date
    Dec 2010
    Posts
    18

    Re: Linked List issue / debugging

    Hmm.. that does sound like it could have worked better (or at least made things easier).
    Its a bit late now though :/
    Implementing that would take a complete overhaul of the project and time is at a premium right now.

    As for the memory corruption... I had a sneaking suspision that could be the culprit and I have been going over every line to try and track down where it could be occuring.
    Unfortunately, I couldnt find anything that could be causing it.

    If maybe you have a few minutes to spare, would you mind taking a look at the code if I emailed it to you? its not huge (about 500 lines, but mostly due to switch cases and if's because of the 7 lists).

  7. #7
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Linked List issue / debugging

    Quote Originally Posted by ghostfacelz View Post
    Hmm.. that does sound like it could have worked better (or at least made things easier).
    Yes. Basically, when the std::list class wants to create a new node or remove a node, it calls an "allocate"/"deallocate" function from that template you see as the second parameter. The list doesn't care how that template is implemented, except it must be a well defined interface (the allocator interface, which you can google easily to see what's required).

    So replacing that template with your own template, and then creating your own allocate() and deallocate() function, would probably have done the trick (given that you know how to use the memory pool you have and return what list is requesting).

    All of those other functions that link previous nodes with next nodes and checking for NULL, etc. -- there is no need for that as the std::list does that for you already. So basically, you would have used std::list to do the "list" work, and your allocator to do the work of supplying the memory for the node data.

    If maybe you have a few minutes to spare, would you mind taking a look at the code if I emailed it to you? its not huge (about 500 lines, but mostly due to switch cases and if's because of the 7 lists).
    You could just zip it up and post it here as an attachment, along with the project (no obj, ncb, or any of those unnecessary files -- only enough to load and compile the project).

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; May 14th, 2011 at 03:57 PM.

  8. #8
    Join Date
    Dec 2010
    Posts
    18

    Re: Linked List issue / debugging

    Thank you so much!
    I really appreciate you taking a look at it.

    So main calls initializeMemoryManager, inside it creates the memoryPoolManager object.
    In constructor is when it calls the initializeLinkList function.
    This is the function im having trouble with.
    (the rest of the functions -allocate, deallocate etc... work, but arent being used at this point, so are irrelevant to my issue)

    If you set a breakpoint at liets say the 64byte list, you will see that the 8byte list isnt linked properly, and the rest are. (its a backwards list, so the next node will be tied to the pPrevious pointer)

    Also, I cant edit the header (one of the criteria)
    Attached Files Attached Files

  9. #9
    Join Date
    Dec 2010
    Posts
    18

    Re: Linked List issue / debugging

    Hasty clean up. Sorry if there are some minor errors due to commenting things out.
    Also mis-spoke, pNext is the next node.

  10. #10
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Linked List issue / debugging

    Quote Originally Posted by ghostfacelz View Post
    If you set a breakpoint at liets say the 64byte list, you will see that the 8byte list isnt linked properly, and the rest are. (its a backwards list, so the next node will be tied to the pPrevious pointer)
    The findChunk() on the deallocate is not working.

    I would suggest debugging this by creating a small pool (not 65,536 bytes, maybe 32 bytes) and then seeing what is causing p8byte to not be correct.

    Regards,

    Paul McKenzie

  11. #11
    Join Date
    Dec 2010
    Posts
    18

    Re: Linked List issue / debugging

    findChunk will cause a memory access issue and cause a break because of the 8byte list not being done correctly. its trying to go through the list and it has a bunch of null pointers.
    (i commented out the deallocate calls in main)
    The 8byte list isnt being created correctly during the initialization, so anthing that accesses that list will cause a fit.
    I have tried a bunch of different ways to debug this problem which is why I came to the forums.

    I have even tried skipping the creation of the 8byte list to see if the same issues occur with the 32byte list....unfortunately it didnt. So the problem I am having is specific to that list and I really have no clue why.

    I havent tried creating a smaller pool, but I think that it will still have the same issue.

    Did you happen to see anything else that might be causing the problem?

    Thanks,
    -

  12. #12
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Linked List issue / debugging

    Quote Originally Posted by ghostfacelz View Post
    I havent tried creating a smaller pool, but I think that it will still have the same issue.
    Right, but the point of creating a small pool is that it is easier to debug. Right now, that function that manipulates the p8Bytes member on initialization is called thousands of times. No human can keep track of that.

    With a smaller sample, it is much easier to see exactly what is happening and why.

    Regards,

    Paul McKenzie

  13. #13
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Linked List issue / debugging

    In addition, looking at how this was coded, you are repeating code over and over again, with the only difference being the chunk size. That class could be much smaller, and more reliable if it were a template, since you would be guaranteed that the same code is used for all chunk sizes. All of those switch statements wouldn't be necessary, and all those different member pointers wouldn't be necessary either.

    Edit: Maybe not even a template -- just pass the chunk size as a parameter when constructing the memory pool class, and use that throughout.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; May 14th, 2011 at 05:34 PM.

  14. #14
    Join Date
    Dec 2010
    Posts
    18

    Re: Linked List issue / debugging

    Maybe not thousands of times, more like 128 times since I set the "chunks" to 128. :P
    But I have been stepping through it to see what changes and when.
    From what I have seen, when the switch hits "case 8:" the p8byte list changes. Which leads me to think that the issue is that pCurrent is still == to p8byte and thats what is causing the problems.
    It almost seems like after leaving local scope, a new address is being assigned, and upon entering the case again, it reverts its pointers back to what it was...or something to that affect.
    That would be fine if that was the case, but then the same things should be happening to the subsequent lists, which it doesnt.

    Im thinking if I/we cant think of what the cause is...i may just have to scrap this and re-do it all using the template you suggested. I just wish I had more time to do so...
    Between implementation and debugging, I may not have time to achieve satisfactory results by monday... which is why I want this to work - its really the last thing that is causing issues with the project.

    Edit: OK, stepping through again, this is exactly what happens.
    first node in p8byte list done fine, last line says p*byte = pCurrent, (added a pCurrent = NULL before the break) breaks
    next node, pCurrent = next memory pool address
    PCurrent next and previous = NULL (should sever any ties to p8byte now)
    hits the switch
    p8byte->next is still being changed?!?!
    It shouldnt be changing anything in p8byte...
    Last edited by ghostfacelz; May 14th, 2011 at 05:59 PM.

  15. #15
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Linked List issue / debugging

    This is a reduced version of your class, but with parameters passed to set up the pool.
    Code:
    #include "MemoryManager.h"
    
    //debug
    #include <iostream>
    using namespace std;
    
    namespace MemoryManager
    {
        // IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT 
        //
        // This is the only static memory that you may use, no other global variables may be
        // created, if you need to save data make it fit in MM_pool
        //
        // IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT
    
    
        const int MM_POOL_SIZE = 65536;
        char MM_pool[MM_POOL_SIZE];
    
        class CMemoryPoolManager
        {
        public:
            CMemoryPoolManager(int numChunks = 128, int chunkSize=8, int offSet=0);
            ~CMemoryPoolManager(){};
            int getChunkSize() const { return m_chunkSize; }
            int getNumChunks() const { return m_numChunks; }
            int getOffset() const { return m_offset; }
            struct MemoryBlock
            {
                bool bInUse;
                short siSize;
                MemoryBlock *pPrevious;
                MemoryBlock *pNext;
            };
    
            //Linked lists
            MemoryBlock *pByte;
            int m_chunkSize;
            int m_numChunks;
            int m_offset;
            char *pMemoryPool;
            bool bInitialize;
    
            //test
            int test;
    
        private:
            void initializeLinkedList(char MM_pool[], int chunks, int chunkSize, int offset);
    
        };
    
        int bestFit(int aSize); //prototype
        bool findChunk(CMemoryPoolManager::MemoryBlock *pCurrent, void *aPointer);
    
        // Initialize set up any data needed to manage the memory pool
        void initializeMemoryManager(void)
        {
            //TEST
            for (int i = 0; i < MM_POOL_SIZE; i++)
                MM_pool[i] = ' ';
            std::cout << sizeof(CMemoryPoolManager) <<endl;
    
            // TODO : IMPLEMENT ME
            CMemoryPoolManager memoryPoolManager; //test
            CMemoryPoolManager *pMemoryPoolManager;
    
            pMemoryPoolManager = (CMemoryPoolManager *) allocate(sizeof(CMemoryPoolManager));
    
            pMemoryPoolManager = &memoryPoolManager;//test
            pMemoryPoolManager->bInitialize = false;
    
            pMemoryPoolManager->pMemoryPool = &MM_pool[0];
    
            pMemoryPoolManager->test = 15;
            *(CMemoryPoolManager *)(&MM_pool[0]) = memoryPoolManager;  
        }
    
        // return a pointer inside the memory pool
        // If no chunk can accommodate aSize call onOutOfMemory()
        void* allocate(int aSize)
        {
            // TODO: IMPLEMENT ME
            if (aSize < 2 || aSize > 16000)
            {
                onIllegalOperation("Allocation size is out of range (2-16000). Size: %d \n", aSize);
                return 0;
            }
    
            CMemoryPoolManager *pMemoryPoolManager;
            pMemoryPoolManager = (CMemoryPoolManager*)MM_pool;	
            int iChunkSize = 0;
    
            if (pMemoryPoolManager->bInitialize)
            {
                pMemoryPoolManager->bInitialize = false;
                char *pCurrent;
                pCurrent = MM_pool;
                return (void *) (pCurrent);
            }
            else
            {
                iChunkSize = bestFit(aSize);
    
                if(pMemoryPoolManager->pByte == NULL)
                    iChunkSize = pMemoryPoolManager->getChunkSize();
    
                CMemoryPoolManager::MemoryBlock *pCurrent;
                pCurrent = pMemoryPoolManager->pByte;
                while (pCurrent != NULL && pCurrent->bInUse == true)
                {
                    pCurrent = pCurrent->pNext;
                }
                pCurrent->bInUse = true;
                return (void *) (pCurrent);
            }//end else
        }
    
        // Free up a chunk previously allocated
        void deallocate(void* aPointer)
        {
            // TODO: IMPLEMENT ME
            CMemoryPoolManager *pMemoryPoolManager;
            pMemoryPoolManager = (CMemoryPoolManager*)MM_pool;	
            CMemoryPoolManager::MemoryBlock *pCurrent;
            bool bChunkFound = false;
    
            if (!bChunkFound)
            {
                pCurrent = pMemoryPoolManager->pByte;
                bChunkFound = findChunk(pCurrent, aPointer);
            }
        }
    
        //---
        //--- support routines
        //--- 
    
        // Will scan the memory pool and return the total free space remaining
        int freeRemaining(void)
        {	
            // TODO: IMPLEMENT ME
            int iFreeRemaining = 0;
            CMemoryPoolManager *pMemoryPoolManager;
            pMemoryPoolManager = (CMemoryPoolManager*)MM_pool;
            CMemoryPoolManager::MemoryBlock *pCurrent;
    
            pCurrent = pMemoryPoolManager->pByte;
            while (pCurrent != NULL) {
                if (!pCurrent->bInUse) iFreeRemaining += pMemoryPoolManager->getChunkSize();
                pCurrent = pCurrent->pNext;
            }
    
            return iFreeRemaining;
        }
    
        // Will scan the memory pool and return the largest free space remaining
        int largestFree(void)
        {
            // TODO: IMPLEMENT ME
            CMemoryPoolManager *pMemoryPoolManager;
            pMemoryPoolManager = (CMemoryPoolManager*)MM_pool;
            CMemoryPoolManager::MemoryBlock *pCurrent;
    
            pCurrent = pMemoryPoolManager->pByte;
            while (pCurrent != NULL) 
            {
                if (!pCurrent->bInUse) 
                    return pCurrent->siSize;
                pCurrent = pCurrent->pNext;
            }
            return 0;
        }
    
        // will scan the memory pool and return the smallest free space remaining
        int smallestFree(void)
        {
            // TODO: IMPLEMENT ME
            CMemoryPoolManager *pMemoryPoolManager;
            pMemoryPoolManager = (CMemoryPoolManager*)MM_pool;
            CMemoryPoolManager::MemoryBlock *pCurrent;
    
            pCurrent = pMemoryPoolManager->pByte;
            while (pCurrent != NULL) 
            {
                if (!pCurrent->bInUse) return pCurrent->siSize;
                pCurrent = pCurrent->pNext;
            }
            return 0;
        }
    
        CMemoryPoolManager::CMemoryPoolManager(int numChunks, int chunkSize, int offSet) :
         pByte(0), m_numChunks(numChunks), m_chunkSize(chunkSize), m_offset(offSet)
        {
            pMemoryPool = MM_pool;
            std::cout << &MM_pool << endl;
            initializeLinkedList(MM_pool, m_numChunks, m_chunkSize, m_offset);
        }
    
        void CMemoryPoolManager::initializeLinkedList(char MM_pool[], int chunks, int chunkSize, int offset)
        {
            MemoryBlock current;
            MemoryBlock *pCurrent = NULL;
            pCurrent = &current;
    
            for (int i=0; i < chunks; i++)
            {
                pCurrent = (MemoryBlock *)&MM_pool[sizeof(CMemoryPoolManager) +1 + (i * chunkSize) + offset];
                pCurrent->pNext = NULL;
                pCurrent->pPrevious = NULL;
                pCurrent->bInUse = false;
    
                pCurrent->siSize = chunkSize;
                pCurrent->pNext = pByte;
                if (pByte != NULL)
                    pByte->pPrevious = pCurrent;
                pByte = pCurrent;
            }
        }
    
        int bestFit(int aSize)
        {
            CMemoryPoolManager *pMemoryPoolManager;
            pMemoryPoolManager = (CMemoryPoolManager*)MM_pool;
            CMemoryPoolManager::MemoryBlock *pCurrent;
            bool bFitFound = false;
            int iChunkSize = 0;
    
            if (!bFitFound)
            {
                pCurrent = pMemoryPoolManager->pByte;
                while (pCurrent != NULL && !bFitFound) 
                {
                    if (pCurrent->bInUse) 
                        pCurrent = pCurrent->pNext;
                    else
                    {
                        bFitFound = true;
                        iChunkSize = aSize;
                    }
                }
            }
            return iChunkSize;
        }
    
        bool findChunk(CMemoryPoolManager::MemoryBlock *pCurrent, void *aPointer)
        {
            bool bChunkFound = false;
    
            while (pCurrent != NULL && !bChunkFound)
            {
                if (pCurrent == aPointer)
                {
                    bChunkFound = true;
                    pCurrent->bInUse = false;
                }
                else
                    pCurrent = pCurrent->pNext;
            }
            return bChunkFound;
        }
    }//end namespace
    It defaults to 8 byte chunks, with 128. I basically removed all switch() statements, all the pointers (except for 1), and added three member variables. The constructor for the memory pool has default arguments.

    Regards,

    Paul McKenzie

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center