Jump to content
  • Advertisement
Amir_r_KB

C++ Custom "Vector" Container Heap Corruption

Recommended Posts

Posted (edited)

Hi, I just implemented my first resizable container ( std::vector ) and it broke on the first attempt lol!

Heap corruption is caught when the assignment operator attempts to free() old data, and it works fine without free() , which of course is a leak.

 

Here's the use case : ( simplified from a recursive function ) 

	typedef struct Widget 
	{
		Vec3		 pos;
		float		 width;
		float		 height;
		List<Widget> children;
	};

	List<Widget> list ;

	Widget widget = {};

	widget.children.add (widget); 
	widget.children.add (widget); // Heap corruption when free() is called in assignment operator=()

 Definition :

template <typename T>
struct List
{
	T*	start	 = 0;
	u64 capacity = 0;
	u64 size	 = 0;

	      inline List  ( ) {};
	      inline List  ( u32 count );
	      inline List  ( const List<T>& other ) ;
		  inline ~List ( );

	inline void add     ( T element );
	inline void reserve ( u32 count );
	inline void clear   ();

	inline T& operator[] (u64 x) 
	{
		return start[x];
    }
  
	inline List<T>& operator=( List<T>& other );

};


template <typename T> 
List<T>::List   ( u32 count )
{
	u32 len		= sizeof(T) * count; 
	start		= (T*) malloc ( len );
	size		= 0;
	capacity	= len;
};

template <typename T>
List<T>::List  ( const List<T>& other ) 
{ 
	u64 len		= other.size * sizeof(T) ;

	if ( other.size ) 
	{
		start = (T*) malloc ( len );
		for ( int i=0; i < other.size; i++)
		{
			start[i] = other.start[i];
		}
	}
	size      = other.size;
	capacity  = len;
}

template <typename T> 
List<T>::~List   ( )
{
	if ( start )
		free ( start );
};

template <typename T> 
List<T>& List<T>::operator=( List<T>& other )
{ 
	u64 len	= other.size * sizeof(T) ;
	
	if ( other.size ) 
	{
		if ( start )
			free ( start );  // Corruption exception from here

		start = (T*) malloc ( len );
		for ( int i=0; i < other.size; i++)
		{
			start[i] = other[i];
		}
	}
	size      = other.size;
	capacity  = len;

	return *this;	
}

template <typename T> 
inline void List<T>::add   ( T element )
{ 
	if ( !start )
	{ 
		reserve ( 1 );
		start[size] = element;
		size++;

		return;
	}

	if ( size >= ( capacity / sizeof(T) ) )
	{
		reserve ( size + 1 );
	}
	
	start[size] = element;
	size++;
};

template <typename T> 
inline void List<T>::reserve   ( u32 count )
{ 	
	if ( count == 0 )
	{
		clear();
		return;
	}
	if ( count == size )
	{
		return;
	}

	T* old	 = start;
	u64 len  = sizeof(T) * count * 2;
	start    = (T*) malloc ( len );

	for ( int i=0; i < size; i++)
	{
		start[i] = old[i];
	}
	
	capacity	= len;

	if ( old )
		free ( old );
}

template <typename T> 
inline void List<T>::clear ()
{
	if ( start )
		free ( start );
	size		= 0;
	capacity	= 0;
};

For some reason it sometimes works without any exceptions being thrown..

Edited by Amir_r_KB

Share this post


Link to post
Share on other sites
Advertisement
Posted (edited)

First, is there a reason you're not using std::vector?

One problem might be that clear() does not set "start" to nullptr, where other member functions like add() inspect "start". 

Another problem is that add(...) calls T::operator=(...) on the element to be constructed, but that element will not be initialised. You should use placement new.

Something I find a bit confusing is that the "size" appears to count elements, whereas "capacity" appears to be in bytes. I think using elements for both would be simpler to reason about, and then you can convert to bytes when calling malloc(...). I also find the name "start" a little confusing, something like "elements" might be clearer.

Obviously it depends on what you've defined the member function to mean, but most containers have separate resize(...) and reserve(...) member functions, with the former potentially destructive (it could reduce the number of elements in the container) and the latter will only ensure the capacity is sufficient, it will never result in the container having less elements.

Something that will simplify your program is to avoid a null check before calling free(...), free() is null safe.

Another thing to think about is exception safety. For example, in your operator=(...), should there be an exception when the elements are being copied, your List becomes corrupted. Exception safety in general is very difficult in C++, to be fully exception safe and avoid a memory leak you'd also need to destroy the partially constructed elements during the copy, but memory corruption could open you up to security issues, particularly if your game interacts with untrusted data (e.g. multiplayer, or even just downloading custom maps / mods).

Edited by rip-off
Formatting improvments

Share this post


Link to post
Share on other sites
16 minutes ago, rip-off said:

First, is there a reason you're not using std::vector?

Mainly out of curiosity and also the verbosity of STL, the syntax looks awful to me. Although i'm aware of the downsides of making a new one. 

 

1 hour ago, rip-off said:

Another problem is that add(...) calls T::operator=(...) on the element to be constructed, but that element will not be initialised. You should use placement new.

Thanks a ton! that was the issue. I didn't even know about placement new!

 

1 hour ago, rip-off said:

Something I find a bit confusing is that the "size" appears to count elements, whereas "capacity" appears to be in bytes. I think using elements for both would be simpler to reason about, and then you can convert to bytes when calling malloc(...). I also find the name "start" a little confusing, something like "elements" might be clearer.

Obviously it depends on what you've defined the member function to mean, but most containers have separate resize(...) and reserve(...) member functions, with the former potentially destructive (it could reduce the number of elements in the container) and the latter will only ensure the capacity is sufficient, it will never result in the container having less elements.

True i'll change them.

2 hours ago, rip-off said:

Another thing to think about is exception safety. For example, in your operator=(...), should there be an exception when the elements are being copied, your List becomes corrupted. Exception safety in general is very difficult in C++, to be fully exception safe and avoid a memory leak you'd also need to destroy the partially constructed elements during the copy, but memory corruption could open you up to security issues, particularly if your game interacts with untrusted data (e.g. multiplayer, or even just downloading custom maps / mods).

I may be wrong but for now i won't use any exceptions anywhere, to keep things cleaner and avoid their overhead.

 

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!