Serious placement new bugs

mreuvers
Posts: 69
Joined: Sat May 10, 2008 8:39 am

Serious placement new bugs

Post by mreuvers »

Hi there,

We've encountered some really nasty bugs that are present throughout the Bullet code. Currently Bullet's way of constructing a lot of arrays is with a placement new. Something like the following example:

Code: Select all

void *ptr = btAlignedAlloc(btAlignedAlloc(sizeof(Handle)*maxHandles,16);
m_pHandles = new(ptr) Handle[maxHandles];
And its way of freeing that memory is this:

Code: Select all

btAlignedFree(m_pHandles);
(see btAxissweep3.h for instance)

However C++ doesn't require that the pointer of the reserved block pointer equals the pointer of the array. In this case ptr == m_pHandles doesn't have to be true! C++ allows compilers to add padding info for their arrays. In this particular case our compiler pads the base address ptr with 16 bytes array information, yielding a m_pHandles that equals ptr + 16. This is compiler specific and doesn't apply to the vstudio compiler.

So if you then do a btAlignedFree on m_pHandles, things will go horribly wrong. What *should* happen is that you free the pointer returned by btAlignedAlloc, not the pointer returned by the placement new!

More info: http://www.parashift.com/c++-faq-lite/c ... l#faq-38.7

Unfortunately a quite involved fix will be required to get rid of this behavior :( On a general remark: properly handling placement news, with all its quirks, is difficult and therefore I personally always avoid using them.

Cheers,


Martijn
mreuvers
Posts: 69
Joined: Sat May 10, 2008 8:39 am

Re: Serious placement new bugs

Post by mreuvers »

Fortunately I only found three problem cases in which a placement new was used to create an array. I fixed them by also keeping track of the raw pointer and calling free on that. Patch below, enjoy!

Another problem introduced by the compiler adding padding, is that you also need to account for that when allocating your memory. For instance if you do this:

Code: Select all

void *ptr = btAlignedAlloc(btAlignedAlloc(sizeof(Handle)*maxHandles,16);
m_pHandles = new(ptr) Handle[maxHandles];
and the compiler adds 16 bytes padding, you didn't reserve enough memory to begin with. If you then traverse through the array, the last item of the array will be out of bounds. Therefore make 100% sure you account for the padding in the btAlignedAllocInternal and btAlignedAlloc functions!

Cheers,


Martijn

Code: Select all

Index: btAxisSweep3.h
===================================================================
--- btAxisSweep3.h	(revision 1223)
+++ btAxisSweep3.h	(working copy)
@@ -77,9 +77,11 @@
 	BP_FP_INT_TYPE m_numHandles;						// number of active handles
 	BP_FP_INT_TYPE m_maxHandles;						// max number of handles
 	Handle* m_pHandles;						// handles pool
+	void* m_pHandlesRawPtr;
 	BP_FP_INT_TYPE m_firstFreeHandle;		// free handles list
 
 	Edge* m_pEdges[3];						// edge arrays for the 3 axes (each array has m_maxHandles * 2 + 2 sentinel entries)
+	void* m_pEdgesRawPtr[3];
 
 	btOverlappingPairCache* m_pairCache;
 
@@ -269,8 +271,9 @@
 	m_quantize = btVector3(btScalar(maxInt),btScalar(maxInt),btScalar(maxInt)) / aabbSize;
 
 	// allocate handles buffer and put all handles on free list
-	void* ptr = btAlignedAlloc(sizeof(Handle)*maxHandles,16);
-	m_pHandles = new(ptr) Handle[maxHandles];
+	m_pHandlesRawPtr = btAlignedAlloc(sizeof(Handle)*maxHandles,16);
+	m_pHandles = new(m_pHandlesRawPtr) Handle[maxHandles];
+
 	m_maxHandles = maxHandles;
 	m_numHandles = 0;
 
@@ -286,8 +289,8 @@
 		// allocate edge buffers
 		for (int i = 0; i < 3; i++)
 		{
-			void* ptr = btAlignedAlloc(sizeof(Edge)*maxHandles*2,16);
-			m_pEdges[i] = new(ptr) Edge[maxHandles * 2];
+			m_pEdgesRawPtr[i] = btAlignedAlloc(sizeof(Edge)*maxHandles*2,16);
+			m_pEdges[i] = new(m_pEdgesRawPtr[i]) Edge[maxHandles * 2];
 		}
 	}
 	//removed overlap management
@@ -310,18 +313,16 @@
 #endif //DEBUG_BROADPHASE
 
 	}
-
 }
 
 template <typename BP_FP_INT_TYPE>
 btAxisSweep3Internal<BP_FP_INT_TYPE>::~btAxisSweep3Internal()
-{
-	
+{	
 	for (int i = 2; i >= 0; i--)
 	{
-		btAlignedFree(m_pEdges[i]);
+		btAlignedFree(m_pEdgesRawPtr[i]);
 	}
-	btAlignedFree(m_pHandles);
+	btAlignedFree(m_pHandlesRawPtr);
 
 	if (m_ownsPairCache)
 	{
Index: btSimpleBroadphase.cpp
===================================================================
--- btSimpleBroadphase.cpp	(revision 1223)
+++ btSimpleBroadphase.cpp	(working copy)
@@ -50,8 +50,9 @@
 	}
 
 	// allocate handles buffer and put all handles on free list
-	void* ptr = btAlignedAlloc(sizeof(btSimpleBroadphaseProxy)*maxProxies,16);
-	m_pHandles = new(ptr) btSimpleBroadphaseProxy[maxProxies];
+	m_pHandlesRawPtr = btAlignedAlloc(sizeof(btSimpleBroadphaseProxy)*maxProxies,16);
+	m_pHandles = new(m_pHandlesRawPtr) btSimpleBroadphaseProxy[maxProxies];
+
 	m_maxHandles = maxProxies;
 	m_numHandles = 0;
 	m_firstFreeHandle = 0;
@@ -73,7 +74,7 @@
 
 btSimpleBroadphase::~btSimpleBroadphase()
 {
-	btAlignedFree(m_pHandles);
+	btAlignedFree(m_pHandlesRawPtr);
 
 	if (m_ownsPairCache)
 	{
Index: btSimpleBroadphase.h
===================================================================
--- btSimpleBroadphase.h	(revision 1223)
+++ btSimpleBroadphase.h	(working copy)
@@ -59,6 +59,7 @@
 	int		m_numHandles;						// number of active handles
 	int		m_maxHandles;						// max number of handles
 	btSimpleBroadphaseProxy* m_pHandles;						// handles pool
+	void* m_pHandlesRawPtr;
 	int		m_firstFreeHandle;		// free handles list
 	int		m_firstAllocatedHandle;
 
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA

Re: Serious placement new bugs

Post by Erwin Coumans »

We will verify and sort it out asap. We prepare for SIGGRAPH, so expect some delay:
http://code.google.com/p/bullet/issues/ ... &thanks=69

By the way, the patch format doesn't work with TortoiseSVN client. What patch/diff version/platform did you use to create the patch?

Thanks a lot for the report and fix,
Erwin
mreuvers
Posts: 69
Joined: Sat May 10, 2008 8:39 am

Re: Serious placement new bugs

Post by mreuvers »

How odd, I simply copy/pasted it from a .patch file (Tortoise). Is it perhaps possible to enable file attachments with the extension .patch in this forum?
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA

Re: Serious placement new bugs

Post by Erwin Coumans »

It would be good to keep the patches organized in the googlecode issue tracker, and leave the discussion in this forum.
Typically you start discussion in this forum here, and if changes/patches are required, file an issue at googlecode.

That makes life easier for us,
Thanks,
Erwin
Quarob
Posts: 5
Joined: Thu Aug 07, 2008 1:41 pm

Re: Serious placement new bugs

Post by Quarob »

Hello guys,

I started using Bullet in our game (Wii) just two days ago. Everything went smooth, and we are quite happy. The only issue we found was a memory corruption bug when deleting our "btBroadphaseInterface". The patch posted by Martijn works perfectly. Just wanted to confirm this and say "Thanks!".

Rob.
mreuvers
Posts: 69
Joined: Sat May 10, 2008 8:39 am

Re: Serious placement new bugs

Post by mreuvers »

Quarob wrote:Hello guys,

I started using Bullet in our game (Wii) just two days ago. Everything went smooth, and we are quite happy. The only issue we found was a memory corruption bug when deleting our "btBroadphaseInterface". The patch posted by Martijn works perfectly. Just wanted to confirm this and say "Thanks!".

Rob.
Where can I send the bill to? :D
User avatar
John McCutchan
Posts: 133
Joined: Wed Jul 27, 2005 1:05 pm
Location: Berkeley, CA

Re: Serious placement new bugs

Post by John McCutchan »

The reason the patch doesn't work for Erwin is that when viewed in the forum the tab characters are lost. In the future you could attach the patch instead, that way the whitespace is not mangled. I've re-created and committed this patch. Please let us know if you find anymore locations in the Bullet code where this pattern exists.

Thanks,
John