Linked List issue / debugging

[ghostfacelz]

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:

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:

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

[Paul McKenzie]

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

[ghostfacelz]

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.

[Paul McKenzie]

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

[Paul McKenzie]

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.)

std::list<T, allocator>

That is the full definition of std::list.

Regards,

Paul McKenzie

[ghostfacelz]

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).

[Paul McKenzie]

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

[ghostfacelz]

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)

[ghostfacelz]

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

[Paul McKenzie]

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

[ghostfacelz]

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

[Paul McKenzie]

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

[Paul McKenzie]

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

[ghostfacelz]

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

[Paul McKenzie]

This is a reduced version of your class, but with parameters passed to set up the pool.

#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