Switching from vector to deque results in crash upon shutdown?

Started by
4 comments, last by Wolfdog 15 years, 5 months ago
Lately I've gotten a little "memory manager" (not quite complete yet) up and running for my latest project. It was working just fine using an std::vector to keep track of memory "blocks" (which really are just pointers to the objects, with the intent being that upon releasing them I "recycle" them), but tonight I decided to switch it to a deque to see what that would do for my performance. I never got to testing the performance, sadly. I got it working apparently fine in debug mode, but when I switched to release mode, the program would crash upon shutdown. I traced the crash to a single line of code indicating a null pointer was present in a place where it was not before. The methods in question are below:
	
void Release()
{
	if (memory.size())
	{
		// iterate through the deque and remove all uninitialized blocks
		std::deque<Obj>::iterator memoryItor;
		for (memoryItor = memory.begin(); memoryItor != memory.end(); memoryItor++)
		{
			Obj o = (*memoryItor);
			RemoveInstance(o.ptr); // remove the instance
		}
		CollectGarbage(); // call the garbage collector
		numUsed = 0;
		numFree = 0;
	}
}

// remove an instance
void RemoveInstance(T* obj) 
{
	// get the address of the actual object pointer
	Obj* o = (Obj*)obj-sizeof(unsigned int);
	assert(o);
	o->refCount--; // <- fails here
	numUsed--;
	numFree++;
}

And the relevant class members:

private:
	// the actual object that we keep track of
	struct Obj
	{
		unsigned int refCount;
		T* ptr;
	};
	// deque of objects
	std::deque<Obj> memory;
	unsigned int numUsed, numFree;

My question is, what could be causing this apparent null pointer crash? I've seen this happen before upon a switch to release mode from debug mode, but a full rebuild fixed it that time. I tried that and it doesn't seem to be the case here. Switching back to a std::vector via global search and replace seems to fix it. Maybe I shouldn't be switching containers with a global search and replace... I'm thinking there must be something I'm doing wrong with the deque (I haven't used them much before), but I can't think of what it is; the program compiles fine and runs fine until shutdown. And it only happens in release mode. Does anyone have any ideas as to why this crashes in release mode? And what I can do to fix it? I just KNOW I'm doing something stupid with this thing...
Advertisement
Obj* o = (Obj*)obj-sizeof(unsigned int);

Don't have enough information about the allocation but I assume you are trying to back up 4 bytes? This would back up sizeof(Obj) sizeof(unsigned int) times.
Obj* o = (obj*)((char*)obj-sizeof(unsigned int));

Or if Obj is the size of the data you are trying to get to, I assume it only contains a single unsigned int.
Obj* o = (Obj*)obj-1;
Quote:Original post by Wolfdog4
Don't have enough information about the allocation but I assume you are trying to back up 4 bytes?


That's right.

Quote:
Or if Obj is the size of the data you are trying to get to, I assume it only contains a single unsigned int.


No. As is stated in the code I provided, the Obj in question consists of a pointer and a refcount, both of which should be 4 bytes long. The total structure therefore should be 8 bytes long.

This code works fine in debug mode, and it works fine in both debug and release mode when I use a vector instead of a deque.
Ok I wrote that post way too fast and did not clarify myself. So I think I will take another shot at this. My apologies if I just caused more confusion.

Your code:
Obj* o = (Obj*)obj-sizeof(unsigned int);

is roughly equivalent to:
Obj *o = (Obj*)obj; o = &o[-4];

You are backing up 32 bytes. I do not have an answer for why you are seeing any positive results from this, but I do know that you are changing memory you should not be changing. This is the same if you use a vector, list or a simple C array.

That is why I suggested that you cast to char* because that is a single byte array.
Obj* o = (obj*)((char*)obj-sizeof(unsigned int))
The code above does what you are currently trying to do.

Now that I have re-read over this code again I see a few other problems. Your function RemoveInstance takes a pointer and tries to change 4 bytes before it in memory. The first thing is that I see no connection in this code between the address that T* ptr points to and the unsigned int refCount before the T* ptr.

Lets take out all the low level details and try to draw a simple picture here. So we will say that we have a single Obj structure which the deque has allocated for you at address 0x000004.
       0     1     2     3     4     5     6     7     8       +-----------------------+-----------------------+0x0004 | unsigned int refCount | T* ptr                |       +-----------------------+-----------------------+


Ok so now lets say that you allocate with new or malloc some arbitrary 100 bytes of data. You get back a pointer that points to address 0x0244. So you set T* ptr to that address.

                           1 1 1 1 1 1 1 1 1 1 2 2 2 2...       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3...       +----------------------------------------------...0x0244 | Some data filling 100 bytes                  ...        +----------------------------------------------...


So now the T* ptr = 0x0244. That is because you need that pointer to point to the actual memory you are allocating. As you can see here there is a gap between the T* ptr and the address it is pointing to.

So when you call RemoveInstance(o.ptr); What you are doing is RemoveInstance(0x0244); Then your are attempting to back up in memory 4 bytes (although your code backs up 32 so it's even worse) you are changing a value at addres 0x0240. Although undefined I can tell you that at 4 bytes in Win32 debug you are probably writing over fence memory put in place by the crt memory allocation routines but at 32 I can only guess that it's part of the memory header or could end up outside your process's virtual address space. In any case that is bad behavior and you will probably stumble upon some memory that you are not allowed to change and will instead raise an exception.

Now for a solution. Instead of passing in the pointer to RemoveInstance pass in a reference to the object in the deque list.
void Release(){	if (memory.size())	{		// iterate through the deque and remove all uninitialized blocks		std::deque<Obj>::iterator memoryItor;		for (memoryItor = memory.begin(); memoryItor != memory.end(); memoryItor++)		{			Obj &o = (*memoryItor); // <- Changed			RemoveInstance(o); // remove the instance <- Changed		}		CollectGarbage(); // call the garbage collector		numUsed = 0;		numFree = 0;	}}// remove an instancevoid RemoveInstance(Obj &obj) // <- Changed{	obj->refCount--;	numUsed--;	numFree++;}


I am making some assumptions here of what you are doing because you have not provided enough code to get a full picture, so I am filling in the gaps, but I am confident that is your problem.
That makes sense, though I was under the impression that pointer arithmetic worked with bytes, not dwords... Then again, pointer arithmetic isn't something I usually do. And how does that explain why the code worked just fine in both release and debug mode with std::vector and std::list but not std::deque.

With this last code:
// remove an instancevoid RemoveInstance(Obj &obj) // <- Changed{	obj->refCount--;	numUsed--;	numFree++;}


I could have used an Obj as a parameter in the first place, but the whole point of the exercise was that I feed the manager the actual pointer to the data being referenced. Basically, I want RemoveInstance() to behave like a glorified free(). Hence why I'm jumping through all those pointer arithmetic hoops. :P

Would it be better for my purposes if I were to switch the order of members in the Obj struct so that the pointer was first, and then from there I could increment the pointer by 4 bytes instead of trying to go backwards?
Quote:Original post by Oberon_Command
That makes sense, though I was under the impression that pointer arithmetic worked with bytes, not dwords... Then again, pointer arithmetic isn't something I usually do.

No it works based on the size of the pointer's type. If you had a pointer to a structure that held 10k of data and incremented a pointer to one you would increment 10k bytes instead of 1.

Quote:And how does that explain why the code worked just fine in both release and debug mode with std::vector and std::list but not std::deque.

That I cannot explain.

Quote:Would it be better for my purposes if I were to switch the order of members in the Obj struct so that the pointer was first, and then from there I could increment the pointer by 4 bytes instead of trying to go backwards?

No that would not change anything. The two blocks of memory are still spaced an undefined amount away from each other.

Quote:
I could have used an Obj as a parameter in the first place, but the whole point of the exercise was that I feed the manager the actual pointer to the data being referenced. Basically, I want RemoveInstance() to behave like a glorified free(). Hence why I'm jumping through all those pointer arithmetic hoops. :P


I can give a quick example, although I do not recommend it. You should use the obj instead.
#include <stdlib.h>// Make it something you can see in memory debuggers#define FENCE_HEX 0xABAAAAAB// Notice that the structure is a multiple of 8 bytes,// malloc guarentees 8 byte alignment on 32 bit// systems. You must keep that guarantee with// your allocator. To support 64 bit you must have// 16 byte alignment.struct MemHeader{	unsigned int size;	unsigned int allocCount;	char *Ptr;	// The fence can be used to warn about buffer under-runs	// and buffer over-runs. This is something the debug crt	// does in windows but you do not need to do it. Although	// if you do replace malloc with your own functions using	// the HeapAlloc function it would be a good idea.	int fence;	// char Data[n];   // int end_fence;};// Global allocation count.unsigned int allocNum = 0;void *allocateMem ( unsigned int size ){	// The trick is to put all the memory into on single block.	// We need the size of the header + size of data + 4 for the	// ending fence	MemHeader *Header = (MemHeader *)malloc(sizeof(MemHeader)+size+4);	Header->size = size;	Header->allocCount = ++allocNum;	Header->fence = FENCE_HEX;	// Trick number 2 is to return the pointer after your header	Header->Ptr = (char*)(Header+1);	// Now you can set the ending fence	(*(int*)(Header->Ptr+size)) = FENCE_HEX;	// Give the user the pointer and they won't care about the data before or after it.	return Header->Ptr;}void freeMem ( void *ptr ){	// Although only delete guarentees safty with NULL it's nice to do so with your allocator	// but an assert here would be a good idea	if (ptr == NULL)		return;	// Check the buffer under-run fence before trying to access the header, of course	// this only protects you from small buffer under-runs.	if (*((int*)ptr-1) != FENCE_HEX)	{		// Some sort of error, exception somehow inform about the bad memory/pointer		return;	}	MemHeader *Header = (MemHeader*)ptr-1;	// Check the buffer over-run fence, it might actually be better to check this	// as an array of bytes due to alignment, but that is outside the scope of	// this example	if (*((int*)((char*)Header->Ptr+Header->size)) != FENCE_HEX)	{		// Some sort of error, exception somehow inform about the bad possible state		// of the heap from writing outside user allocated memory		return;	}	// Notice that we free the header not the pointer returned by the user. This is	// due to it all being a single allocated block.	free(Header);}int main (int /*argc*/, char * /*argv[]*/){	char *testData = (char *)allocateMem(50);	freeMem(testData);	return 0;}


You could then override new and delete and have them use your allocator. Just don't forget to override new[] and delete[].

This topic is closed to new replies.

Advertisement