Sign in to follow this  
Daniel Protopopov

Memory leak troubles

Recommended Posts

Hi there everyone, second day I'm trying to nail down the problem of memory leaks inside my application. What I have is 2 arrays in which I store class pointers and on which I operate. What I am trying to achieve is to detect when object is dead or a duplicate, and do actions from there on. If object is duplicate, I remove old duplicate from Previous array, delete it, and place new duplicate into it. If object doesn't exist in new array, but exists in old, I know for sure that it has been destroyed. I set flag to true and put it into Out array to be sent and notify the program. If it doesn't exist in Prev array, I know it's a new object and place it into Out array to be sent away for notification. This is the code for it:
void CRefreshRequest::Optimize(const char *pcObjectType, list<IResponse *> *pPrevResponses, list<IResponse *> *pNewResponses, list<IResponse *> *pOutResponses)
{
	if(pPrevResponses == NULL || pNewResponses == NULL || pOutResponses == NULL)
		return;

	int iCount = pOutResponses->size();

	// Check - exists in new, but doesn't exist in old
	for(list<IResponse *>::iterator pIter = pNewResponses->begin(); pIter != pNewResponses->end();)
	{
		bool bFound = false;
		for(list<IResponse *>::iterator pPrevIter = pPrevResponses->begin(); pPrevIter != pPrevResponses->end();)
		{
			if((*pPrevIter)->ID == (*pIter)->ID)
			{
				// Exists in both new and old (exists)
				bFound = true;
				SAFEDEL(*pPrevIter);				// Erase and delete old and duplicate data in previously stored array spot
				pPrevIter = pPrevResponses->erase(pPrevIter);

				pOutResponses->push_back(*pIter); // Copy actual data across
				pIter = pNewResponses->erase(pIter); // remove data reference

				break;
			}
		
			if(pPrevIter != pPrevResponses->end())
				pPrevIter++;
		}

		if(!bFound)	// Exists in new but not old (new)
		{
			pOutResponses->push_back(*pIter);	// Copy actual data across
			pIter = pNewResponses->erase(pIter); // remove data reference
		}
		else
		{
			if(pIter != pNewResponses->end())
				pIter++;
		}
	}

	// Check - exists in old, but doesn't exist in new
	for(list<IResponse *>::iterator pPrevIter = pPrevResponses->begin(); pPrevIter != pPrevResponses->end();)
	{
		bool bFound = false;
		for(list<IResponse *>::iterator pIter = pNewResponses->begin(); pIter != pNewResponses->end(); pIter++)
		{
			if((*pPrevIter)->ID == (*pIter)->ID)
			{
				bFound = true;
				break;
			}
		}

		if(!bFound)	// Exists in old but not new (delete)
		{
			(*pPrevIter)->Destroyed = true;
			pOutResponses->push_back(*pPrevIter);	// Copy actual data across
			pPrevIter = pPrevResponses->erase(pPrevIter);	// remove data reference
		}
		else
		{
			if(pPrevIter != pPrevResponses->end())
				pPrevIter++;
		}
	}

	CLogger::GetSingleton().Write("Updated %s(s): %i\n", pcObjectType, pOutResponses->size() - iCount);
}

// Send all objects with status inside Out array


I also perform post-sending clean-up of objects to free memory of objects with Destroyed flag on. Here is the code for it:
void Cleanup(list<IResponse *> *pPrevResponses, list<IResponse *> *pResponses, eResponseType ResponseType)
{
	if(pPrevResponses == NULL || pResponses == NULL)
		return;

	// Copy data from sent data into previous array types
	for(std::list<IResponse *>::iterator pIter = pPrevResponses->begin(); pIter != pPrevResponses->end();)
	{
		if((*pIter)->Destroyed == true)
		{
			delete *pIter;
			pIter = pPrevResponses->erase(pIter);
		}
		else
		{
			if(pIter != pPrevResponses->end())
				pIter++;
		}
	}
	// Copy data from sent data into previous array types
	for(std::list<IResponse *>::iterator pIter = pResponses->begin(); pIter != pResponses->end();)
	{
		if((*pIter)->ResponseType & ResponseType)
		{
			pPrevResponses->push_back(*pIter);
			pIter = pResponses->erase(pIter);
		}
		else
		{
			if(pIter != pResponses->end())
				pIter++;
		}
	}

	// Delete duplicates
	// pPrevResponses->remove_if(DeleteIfDestroyed);
}

The problem is that I'm still getting memory leaks at point where objects are allocated and placed into pNewResponses array (where I populate data anew); although I thought that I covered all necessary data relocations and deletions, it still gives me leaks. I need your help with this one, as my eye may be too worn out in last two days and I just can't pin-point where the problem is. Thank you.

Share this post


Link to post
Share on other sites
Is there any reason you're storing pointers in the lists instead of objects? You'll make a lot of leaks disappear by following the rule of three with your object type, and storing the objects directly instead of by pointer.

In order to work out where the leak is occurring, it would help to see the definition of IResponse, also the macro SAFEDEL.

Your input parameters could be passed by reference instead of by pointer.

I've worked with code that in many places needs to find items that are in one container but not in another, and what you have is probably not the best way to do it.
Algorithmically that code is O(n*m) because you are checking every item against every other item.

The better option would be to store the items in a std::set instead of a std::list. Then you can use the function set_difference to easily get the desired sets of items in O(n+m) time. Much faster!
Unfortunately there is no easy way to get both the sets A-B and B-A. set_symmetric_difference will give you both, but it puts them all in one set. Sometimes this is what I've wanted, but sometimes I need to keep them apart. It could work for you though, so look into it anyway.

An alternative improvement would be to keep them as lists sorted by ID and then iterate over both at the same time. Look into the code for something like set_symmetric_difference for how to do that.

[Edited by - iMalc on July 7, 2008 3:35:58 AM]

Share this post


Link to post
Share on other sites
Try implementing a memory tracker. The GDK project im working on has a gdknew macro that evaluates in debug mode to be new (__FILE__, __LINE__, __FUNCTION__) so you just use gdknew instead of the new keyword.

You can redefine the new keyword as a macro but that can break things.

Here's a quick way of impementing a memory tracker and works very well for the project I'm doing (mines a little more developed/organised tho).

#include <map>

#ifdef _DEBUG
#define new_ new (__FILE__, __LINE__, __FUNCTION__)
#else
#define new_ new
#endif

// implement new operator(s)
void* operator new (size_t sz, const char* file, int line, const char* func)
{
return MemTracker::Alloc (sz, file, line, func);
}

void operator new[] (...) {...}

// implement delete operator(s)
void operator delete (void* p)
{
memTrack->Free (p);
}

// implementation of MemTracker::Alloc
void* MemTracker::Alloc (size_t sz, const char* file, int line, const char* func)
{
void* ptr = malloc (sz);
ASSERT (ptr);

// setup allocation info structure
Allocation al;
al.line = line;
al.file = file; // these are constant string at compile time, no need to assign to an std::string
al.func = func;
allocs[ptr] = al;

return ptr;
}

// implementation of MemTracker::Free
void MemTracker::Free (void* ptr)
{
std::map <void*, Allocation>::iterator al = allocs.find (ptr);
ASSERT (al != allocs.end());
free (ptr);
allocs.erase (ptr);
}

// implement a function to print the undeleted allocations to a log file at program exit
void MemTracker::LogLeaks (void)
{
...
}

Share this post


Link to post
Share on other sites
Thank you both for your replies.
iMalc: SAFEDEL macro is defined as follows:

#define SAFEDEL(x) if(x !=NULL) {delete x; x = NULL;}



Unfortunately I'm forced to store object pointers due to polymorphism.
thre3dee:
I've already used FlipCode' old method and it points me to places where new operator was used for objects stored in lists.

All in all I'm coming towards a decision of using intrusive container I had before, ala boost::intrusive::list, where each object stores pointers to prev and next. Not yet sure if that would help, however I just can't understand why memory deallocation on pointer would result in memory leak. As far as I know, lists store copies of T inside, and as far as I deallocate original memory from heap and erase all entries in list with them I should be fine... That's what confused me.

Share this post


Link to post
Share on other sites
A clean way to get polymorphic behavior with STL containers without having to worry too much about memory management is to use containers of shared pointers (boost::shared_ptr). There is some overhead, but it is acceptable in many situations. There is also the Boost Pointer Container Library, but I haven't used it myself.

Share this post


Link to post
Share on other sites
1) Passing pointers to the lists is really bad here. The caller doesn't get any feedback if the pointers are in fact NULL - except that "nothing happens" - and it's clearly an error on the part of the calling code to do so. Meanwhile, you take more work upon yourself by having to check for the NULLs and then use ->'s everywhere. Solution: pass references instead.

2) The ObjectType argument only gets used for logging, which itself is badly implemented (using a singleton for probably very suspect reasons, and using a very dangerous printf-style interface for probably even more suspect reasons).

3) The Hungarian notation is awkward, too. Use the language's type system to help you, instead of fighting it, and you will find you don't need such ugliness any more. And anyway, iterators aren't pointers, but rather the other way around, so...

4) Let's simplify the logic with a little analysis.

If the object is in neither old nor new, there is nothing to do (obviously).
If the object is in new, but not in old, we move from new to out.
If the object is in old, but not in new, we mark the object as Destroyed, and move from old to out.
If the object is in both new and old, we move from new to out, and delete from old.

Notice that objects are moved from new to out regardless. Therefore, we only need to figure out what to do with old responses, and we can just move all the new ones to the out-list in one chunk (since in the original code, old, destroyed responses are added after all new ones). And as it happens, lists provide a convenient way to make this kind of block transfer, relying on how the linked list is constructed: we simply "splice" the new list into the out list.

(By the way, your "copy actual data across" comments are wrong: what is actually copied is the pointer, and then the original copy is erased from the other list. If the actual IResponse object were copied, you'd need to destroy the original to avoid a leak...)

Then, for each old object we check if it's in the new list. If it is, we erase it entirely; otherwise, we move it across, marking it as Destroyed.

Now, this is all assuming that no objects are "shared" between lists (except temporarily as you move pointers between them). If you are trying to share stuff, well, you're probably screwed and require redesign. :)

Not tested, but...


typedef std::list<IResponse*> responseList;
typedef responseList::iterator responseIter;

struct same_id {
int ID;
same_id(IResponse* reference): ID(reference->ID);
bool operator()(const IResponse* candidate) { return candidate->ID == ID; }
};

void CRefreshRequest::Optimize(
responseList& prevResponses,
responseList& newResponses,
responseList& outResponses
) {
// We're going to want to iterate over the "new responses" after moving them,
// so save an iterator to that list (splice() guarantees it will remain valid).
responseIter newIt = newResponses.begin();
outResponses.splice(newIt, newResponses);

for (responseIter prevIt = prevResponses.begin(); prevIt != prevResponses.end(); prevIt = prevResponses.erase(prevIt)) {
IResponse* prevPtr = *prevIt;
if (std::find_if(newIt, outResponses.end(), same_id(prevPtr)) {
// found the old object in the new list: delete it immediately.
SAFEDEL(prevPtr);
} else {
// didn't find it: copy pointer into the out list and mark object destroyed.
prevPtr->Destroyed = true;
outResponses.push_back(prevPtr);
}
}
}

void loggedOptimization(
CRefreshRequest& optimizer,
responseList& prevResponses,
responseList& newResponses,
responseList& outResponses,
const std::string& objectType
) {
int count = outResponses.size();
optimizer.Optimize(prevResponses, newResponses, outResponses);
// stand-in until we can design a proper logger.
std::cerr << "Updated " << objectType << "(s): " << outResponses.size() - count << std::endl;
}

IResponse* handleDestroyed(IResponse* i) {
if (i->Destroyed) {
delete i;
return NULL;
}
return i;
}

void Cleanup(responseList& prevResponses, responseList& responses, eResponseType ResponseType) {
// We make use of the delete-and-null function to simplify the logic here:
// we replace pointers to deleted instances with nulls, and then sweep out
// the nulls.
std::transform(prevResponses.begin(), prevResponses.end(), prevResponses.begin(), handleDestroyed);
prevResponses.remove(NULL);

for (responseIter iter = responses.begin(); iter != responses.end();) {
IResponse* ptr = *iter;
if (ptr->ResponseType & ResponseType) {
prevResponses->push_back(ptr);
iter = responses->erase(iter);
} else {
// iter *can't* equal responses->end() here.
iter++;
}
}
}



Final thought: could the leak possibly be due to elements remaining in 'responses' when you call Cleanup() and the ResponseType doesn't match?

Share this post


Link to post
Share on other sites
Quote:
Original post by Daniel Protopopov
Thank you both for your replies.
iMalc: SAFEDEL macro is defined as follows:
*** Source Snippet Removed ***

Unfortunately I'm forced to store object pointers due to polymorphism.
thre3dee:
I've already used FlipCode' old method and it points me to places where new operator was used for objects stored in lists.

All in all I'm coming towards a decision of using intrusive container I had before, ala boost::intrusive::list, where each object stores pointers to prev and next. Not yet sure if that would help, however I just can't understand why memory deallocation on pointer would result in memory leak. As far as I know, lists store copies of T inside, and as far as I deallocate original memory from heap and erase all entries in list with them I should be fine... That's what confused me.
Ah okay, well you can remove the "if" in SAFEDEL because it is always safe to delete NULL which is a no-op. Of course if it's not NULL and not valid then checking for NULL doesn't protect you from anything either. So just remove the if.

Share this post


Link to post
Share on other sites
Quote:
Original post by Daniel Protopopov
Thank you both for your replies.
iMalc: SAFEDEL macro is defined as follows:
*** Source Snippet Removed ***

Unfortunately I'm forced to store object pointers due to polymorphism.
thre3dee:
I've already used FlipCode' old method and it points me to places where new operator was used for objects stored in lists.


In the method I explained above you're not storing pointers to actual class types, its merely the allocated chunk of memory which is then constructed and deleted by C++ code generation.

The operator new constructs the pointer returned by your implementation (in this case merely calling malloc).

new Object();

// results in the following code generated
// ptr = return new (sizeof (Object)) { return malloc (size); }
// if (ptr != 0) ptr::Object (); constructor

Share this post


Link to post
Share on other sites
Quote:
Original post by Daniel Protopopov
Also, iterator usage within double for loop is a bit tricky, had to ensure that I'm dereferencing valid iterator, or it gives me an error dialog.


That's why I tried to give you a simplified alternative code structure. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this