overriding new and delete

So, I'm trying to learn how to do custom memory management for keeping track of used memory, leaks and so forth. I read up and did a simple global override just to test out what I had done. For some reason I seem to be getting recursive calls into the new operator. I'm using MinGW on windows 7.

Here are the three files I'm using.

memManage.h

Code:

#include <exception> // for std::bad_alloc
#include <new>
#include <cstdlib> // for malloc() and free()
#include <list>
#include <iostream> //for debugging

#define DEBUG

namespace MemManage {
	extern unsigned long allocated;
	extern std::list<void *> addresses;
	extern std::list<std::size_t> sizes;
}

void* operator new (std::size_t size)throw ( std::bad_alloc );

void operator delete (void *p) throw ();

memManage.cpp

Code:

#include "memManage.h"

unsigned long MemManage::allocated=0;
std::list<void *> MemManage::addresses;
std::list<std::size_t> MemManage::sizes;

void* operator new (std::size_t size) throw ( std::bad_alloc ) {
	#ifdef DEBUG
		std::cout<<"\tallocating\n";
	#endif
	void *p=malloc(size);
	if (p==0)
		throw std::bad_alloc();
	#ifdef DEBUG
		std::cout<<"\t\tpassed first exception\n";
	#endif

	MemManage::allocated+=size;

	if(MemManage::allocated<0) {
		throw std::bad_alloc();
	}
	else	{
		MemManage::addresses.push_back(p);
		MemManage::sizes.push_back(size);
	}
	#ifdef DEBUG
		std::cout<<"\tallocated\n";
	#endif

	return p;
}

void operator delete (void *p) throw () {
	std::list<void*>::iterator aIt=MemManage::addresses.begin();
	std::list<std::size_t>::iterator sIt=MemManage::sizes.begin();

	bool deleted=false;

	for(;aIt != MemManage::addresses.end();) {
		if((*aIt) == p)	{
			deleted=true;
			MemManage::allocated-=*sIt;
			MemManage::addresses.erase(aIt);
			MemManage::sizes.erase(sIt);
		}

		if(deleted) {
			aIt=MemManage::addresses.end();
		}
		else	{
			aIt++;
			sIt++;
		}
	}

	if(!deleted){throw std::bad_alloc();}

	free(p);
}

memTest.cpp

Code:

#include <iostream>
#include <list>
#include "memManage.h"

using namespace std;

int main(int argc, char* argv[]) {
	cout<<MemManage::allocated<<"\n";
	int* test;
	test=new int[10];
	cout<<MemManage::allocated<<"\n";
	delete[] test;
	cout<<MemManage::allocated<<"\n";

	return 0;
}

And here is my abridged output

Code:

0
        allocating
                passed first exception
        allocating
                passed first exception
        allocating
                passed first exception
.
.
.
.
.
        allocating
                passed first exception
        allocating
                passed first exception

   crash

I suppose the problem is that std::list is also using your overridden new, so each allocation causes more allocation to keep track of the previous.

Not sure what would be the best way to avoid this. Perhaps write an allocator for list that doesn't use new?

... crap. So I need to either override new and delete for list or create a class with it's own new and delete operators, right?

Can I just randomly create new and delete operators for list ala

void* std::list::new ( blah blah blah

?

I should probably create a class specifically to handle this so I can still keep track of memory used by list in whatever apps I'm going to profile, right?

A list needs to allocate memory internally (for its nodes), but for that containers specify an allocator parameter (using std::allocator with new by default).

Something like this (copied from standard draft and filled in):

Code:

#include <limits>

template <class T> class mallocator {
public:
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;
    template <class U> struct rebind {
        typedef mallocator<U> other;
    };
    mallocator() throw() {}
    mallocator(const mallocator&) throw() {}
    template <class U> mallocator(const mallocator<U>&) throw() {}
    ~mallocator() throw() {}
    pointer address(reference x) const { return &x; }
    const_pointer address(const_reference x) const { return &x; }
    pointer allocate(size_type n, const void* = 0)
    {
        pointer p = static_cast<pointer>( malloc(n) );
        if (!p) throw std::bad_alloc();
        return p;
    }
    void deallocate(pointer p, size_type) { free(p); }
    size_type max_size() const throw() { return std::numeric_limits<std::size_t>::max(); }

    void construct(pointer p, const_reference v) { new (p) value_type(v); }

    void destroy(pointer p) { p->~value_type(); }
};

and then everywhere:

Code:

std::list<void *, mallocator<void*> >
std::list<std::size_t, mallocator<size_t> >

(typedefs can help)

I'm not sure that I understand what you've put there. I don't see any overrides for new or delete, and I've never made a list using list<T,U>. Is the class mallocator using construct and destruct instead of regular constructors/destructors? Have allocate and deallocate somehow replaced new and delete for this class?

Also, what does this do?

template <class U> struct rebind {
typedef mallocator<U> other;
};

Creates a struct called rebind, which wraps around the mallocator?

All lists are "supposed to" take two template arguments. If you leave the second one off, it uses the default allocator class, which uses new and delete inside the allocate and deallocate functions. (That is to say, the list itself never calls new and delete; the list calls allocate and deallocate, and the default version of allocate calls new.) If you provide the second one, it uses the allocate and deallocate that you provide.

Ah, I see. Thank you very much! I'll try this out asap.

I'm having trouble breaking this up into the header and the cpp file. I've never worked with templates so most of this is gibberish. The errors seem to imply that some of the mallocator functions can't be declared as they are. Anyway, here are the errors, followed by the new files. Note that I haven't incorporated mallocator into the memManage code yet.

Errors

Code:

src\memManage.cpp:79: error: `template<class T> class mallocator' used without template parameters
src\memManage.cpp:79: error: ISO C++ forbids declaration of `mallocator' with no type

src\memManage.cpp: In function `int mallocator()':
src\memManage.cpp:79: error: `int mallocator()' redeclared as different kind of symbol
src\memManage.h:18: error: previous declaration of `template<class T> class mallocator'
src\memManage.h:18: error: previous non-function declaration `template<class T> class mallocator'
src\memManage.cpp:79: error: conflicts with function declaration `int mallocator()'

src\memManage.cpp: At global scope:
src\memManage.cpp:81: error: `template<class T> class mallocator' used without template parameters
src\memManage.cpp:81: error: expected `,' or `...' before '&' token
src\memManage.cpp:81: error: ISO C++ forbids declaration of `mallocator' with no type
src\memManage.cpp:81: error: ISO C++ forbids declaration of `mallocator' with no type

src\memManage.cpp: In function `int mallocator(int)':
src\memManage.cpp:81: error: `int mallocator(int)' redeclared as different kind of symbol
src\memManage.h:18: error: previous declaration of `template<class T> class mallocator'
src\memManage.h:18: error: previous non-function declaration `template<class T> class mallocator'
src\memManage.cpp:81: error: conflicts with function declaration `int mallocator(int)'

src\memManage.cpp: At global scope:
src\memManage.cpp:83: error: `template<class T> class mallocator' used without template parameters
src\memManage.cpp:83: error: ISO C++ forbids declaration of `mallocator' with no type
src\memManage.cpp:83: error: declaration of template `template<class U> int mallocator(const mallocator<U>&)'
src\memManage.h:18: error: conflicts with previous declaration `template<class T> class mallocator'
src\memManage.h:18: error: previous non-function declaration `template<class T> class mallocator'
src\memManage.cpp:83: error: conflicts with function declaration `template<class U> int mallocator(const mallocator<U>&)'
src\memManage.cpp:85: error: expected constructor, destructor, or type conversion before '::' token
src\memManage.cpp:87: error: `template<class T> class mallocator' used without template parameters
src\memManage.cpp:87: error: expected constructor, destructor, or type conversion before "mallocator"
src\memManage.cpp:89: error: `template<class T> class mallocator' used without template parameters
src\memManage.cpp:89: error: expected constructor, destructor, or type conversion before "mallocator"
src\memManage.cpp:91: error: `template<class T> class mallocator' used without template parameters
src\memManage.cpp:91: error: expected constructor, destructor, or type conversion before "mallocator"
src\memManage.cpp:98: error: `template<class T> class mallocator' used without template parameters
src\memManage.cpp:98: error: `template<class T> class mallocator' used without template parameters

memManage.h

Code:

#include <exception> // for std::bad_alloc
#include <new>
#include <cstdlib> // for malloc() and free()
#include <list>
#include <iostream> //for debugging
#include <limits>

#define DEBUG

namespace MemManage
{
	extern unsigned long allocated;
	extern std::list<void *> addresses;
	extern std::list<std::size_t> sizes;
}

template <class T> class mallocator
{
	public:
		typedef size_t size_type;
		typedef ptrdiff_t difference_type;
		typedef T* pointer;
		typedef const T* const_pointer;
		typedef T& reference;
		typedef const T& const_reference;
		typedef T value_type;

		template <class U> struct rebind {
			typedef mallocator<U> other;
		};

		mallocator() throw();

		mallocator(const mallocator&) throw();

		template <class U> mallocator(const mallocator<U>&) throw();

		~mallocator() throw();

		pointer address(reference x) const;

		const_pointer address(const_reference x) const;

		pointer allocate(size_type n, const void* = 0);

		void deallocate(pointer p, size_type);

		size_type max_size() const throw();

		void construct(pointer p, const_reference v);

		void destroy(pointer p);
};

void* operator new (std::size_t size)throw ( std::bad_alloc );

void operator delete (void *p) throw ();

memManage.cpp ... only the mallocator code added at the end of the file

Code:

mallocator::mallocator() throw() {}

mallocator::mallocator(const mallocator&) throw() {}

template <class U> mallocator::mallocator(const mallocator<U>&) throw() {}

mallocator::~mallocator() throw() {}

pointer mallocator::address(reference x) const { return &x; }

const_pointer mallocator::address(const_reference x) const { return &x; }

pointer mallocator::allocate(size_type n, const void* = 0)
{
	pointer p = static_cast<pointer>( malloc(n) );
	if (!p) throw std::bad_alloc();
	return p;
}

void mallocator::deallocate(pointer p, size_type) { free(p); }

size_type mallocator::max_size() const throw() { return std::numeric_limits<std::size_t>::max(); }

void mallocator::construct(pointer p, const_reference v) { new (p) value_type(v); }

void mallocator::destroy(pointer p) { p->~value_type(); }

You have no class called mallocator, so trying to define members of that class isn't going to work. You've got a class called template <class T> mallocator, though.

(You can look at the template tutorial on this very site to get a handle on the syntax.)

I see ... I think. The STL syntax is very intimidating. I can see why new programmers balk at learning it >.> Very ugly.

Thanks.

Okay! Thanks for all the help! I've got it working now, I think. I've only used some new int's to check it, but it works for those, so any other issues I have should be object dependent I guess.

So, in the interest of future searchers, here is what I learned and then the code to prove it.

The basic setup for overriding the global new and delete operators applies to any other object that uses new or delete. Since I wanted to use a list to track allocated memory I had a recursive call to my new ... new. To fix this, we need a custom allocator that uses malloc and free instead of new and delete. The allocator for STL containers can be specified ala "list<T, myAlloc<T> >".

In the interest of keeping everything portable, the allocator is coded using a template. Templates are ugly, but there ya go. When using a template you need to include "template class<T>" in front of any function thats part of the templated class, as the created class is actually "class<T>", and not just "class". The "template class<T>" lets the compiler know what you mean when you use T later. If you have variables or typdefs in your templated class that depend on "T", you need to refer to those using "typename class<T>::variable" instead of just "class<T>::variable". Other than being a standard, I'm not sure exactly what this does for the compiler. If you don't do it you get this error (from g++ anyway) "error: expected constructor, destructor, or type conversion".

Finally, when using free on a pointer, make sure to cast that pointer to a void pointer, ala "free((void*)p)".

And here is the code, with debug statements left in, just in case you wanna see them. Credits are at the bottom of the post.

memManage.h

Code:

#include <exception> // for std::bad_alloc
#include <new>
#include <cstdlib> // for malloc() and free()
#include <list>
#include <iostream> //for debugging
#include <limits>

#define DEBUG

template <class T> class mallocator
{
	public:
		typedef size_t size_type;
		typedef ptrdiff_t difference_type;
		typedef T* pointer;
		typedef const T* const_pointer;
		typedef T& reference;
		typedef const T& const_reference;

		template <class U> struct rebind {
			typedef mallocator<U> other;
		};

		mallocator() throw();

		mallocator(const mallocator&) throw();

		template <class U> mallocator(const mallocator<U>&) throw();

		~mallocator() throw();

		pointer address(reference x) const;

		const_pointer address(const_reference x) const;

		pointer allocate(size_type n, const void* = 0);

		void deallocate(pointer p, size_type);

		size_type max_size() const throw();

		void construct(pointer p, const_reference v);

		void destroy(pointer p);
};

namespace MemManage
{
	extern unsigned long allocated;
	extern std::list<void *, mallocator<void *> > addresses;
	extern std::list<std::size_t, mallocator<std::size_t> > sizes;
}

void* operator new (std::size_t size)throw ( std::bad_alloc );

void operator delete (void *p) throw ();

memManage.cpp

Code:

#include "memManage.h"

using namespace MemManage;

unsigned long MemManage::allocated=0;
std::list<void *, mallocator<void *> > MemManage::addresses;
std::list<std::size_t, mallocator<size_t> > MemManage::sizes;

void* operator new (std::size_t size) throw ( std::bad_alloc )
{
	#ifdef DEBUG
		std::cout<<"\tnew\n\t{\n";
	#endif
	void *p=malloc(size);
	if (p==0) // did malloc succeed?
		throw std::bad_alloc(); // ANSI/ISO compliant behavior

	allocated+=size;

	if(allocated<0)
	{
		throw std::bad_alloc();//we have requested more memory than we can represent in a long integer
	}
	else
	{
		#ifdef DEBUG
			std::cout<<"\t\tAdding to tracking lists\n";
		#endif
		//structure here to store info on allocated memory
		addresses.push_back(p);
		sizes.push_back(size);
	}
	#ifdef DEBUG
		std::cout<<"\t}\n";
	#endif

	return p;
}

void operator delete (void *p) throw ()
{
	//MemManage::allocated-=size;
	std::list<void*,mallocator<void*> >::iterator aIt=addresses.begin();
	std::list<std::size_t,mallocator<std::size_t> >::iterator sIt=sizes.begin();

	#ifdef DEBUG
		std::cout<<"\tdelete\n\t{\n";
	#endif

	bool deleted=false;

	for(;aIt != addresses.end();)
	{
		if((*aIt) == p)
		{
			#ifdef DEBUG
				std::cout<<"\t\tRemoving from tracking lists\n";
			#endif
			deleted=true;
			allocated-=*sIt;
			addresses.erase(aIt);
			sizes.erase(sIt);
		}

		if(deleted)
		{
			aIt=addresses.end();
		}
		else
		{
			aIt++;
			sIt++;
		}
	}

	if(!deleted)
	{
		//this should never happen.
		//if this happens we have a catastrophic failure

		#ifdef DEBUG
			std::cout<<"\tDidn't find the object to delete\n";
		#endif
		throw std::bad_alloc();
	}

	#ifdef DEBUG
		std::cout<<"\t}\n";
	#endif

	free(p);
}

template <class T> mallocator<T>::mallocator() throw() {}

template <class T> mallocator<T>::mallocator(const mallocator&) throw() {}

template <class T> template <class U> mallocator<T>::mallocator(const mallocator<U>&) throw() {}

template <class T> mallocator<T>::~mallocator() throw() {}

template <class T> typename mallocator<T>::pointer mallocator<T>::address(typename mallocator<T>::reference x) const { return &x; }

template <class T> typename mallocator<T>::const_pointer mallocator<T>::address(typename mallocator<T>::const_reference x) const { return &x; }

template <class T> typename mallocator<T>::size_type mallocator<T>::max_size() const throw() { return std::numeric_limits<std::size_t>::max(); }


//allocation and deallocation functions
template <class T> typename mallocator<T>::pointer mallocator<T>::allocate(mallocator<T>::size_type n, const void* z)
{
	#ifdef DEBUG
		std::cout<<"\t\tmallocate\n";
	#endif
	typename mallocator<T>::pointer p = static_cast<typename mallocator<T>::pointer>( malloc(n) );
	if (!p) throw std::bad_alloc();
	#ifdef DEBUG
        std::cout<<"\t\t\tallocate "<< n <<" element(s)"<<" of size "<<sizeof(T)<<"\n\t\t\tallocated at: "<<(void*)p<<"\n";
	#endif
	return p;
}

template <class T> void mallocator<T>::deallocate(typename mallocator<T>::pointer p, typename mallocator<T>::size_type n)
{
	#ifdef DEBUG
		std::cout<<"\t\tmdeallocate\n";
		std::cout<<"\t\t\tdeallocate "<<n<<" element(s) of size "<<sizeof(T)<< " at: "<<(void*)p<<"\n";
	#endif
	free((void*)p);
}

template <class T> void mallocator<T>::construct(typename mallocator<T>::pointer p, typename mallocator<T>::const_reference v)
{
	#ifdef DEBUG
		std::cout<<"\t\tmconstruct\n";
	#endif
	new (p) T(v);
}

template <class T> void mallocator<T>::destroy(typename mallocator<T>::pointer p)
{
	#ifdef DEBUG
		std::cout<<"\t\tmdestroy\n";
	#endif
	p->~T();
}

memTest.cpp

Code:

#include <iostream>
#include "memManage.h"

using namespace std;

int main(int argc, char* argv[])
{

	cout<<MemManage::allocated<<"\n";
	int* test;
	test=new int[10];
	cout<<MemManage::allocated<<"\n";
	delete test;
	cout<<MemManage::allocated<<"\n";
	test=new int[10];
	cout<<MemManage::allocated<<"\n";
	delete[] test;
	cout<<MemManage::allocated<<"\n";

	return 0;
}

Thanks to :
anon and tabstop from cprogramming.com

And the following sites (if external urls are verbotten, delete them and please forgive me)

cprogramming template tutorial
linux questions thread on templates - for typename
memory allocation code - for free((void*)p)

Originally Posted by gesangbaer

Finally, when using free on a pointer, make sure to cast that pointer to a void pointer, ala "free((void*)p)".

That cast is unnecessary.

Well, the program crashes on that function without the cast. Whats the other source of that error?

Originally Posted by gesangbaer

If you have variables or typdefs in your templated class that depend on "T", you need to refer to those using "typename class<T>::variable" instead of just "class<T>::variable". Other than being a standard, I'm not sure exactly what this does for the compiler.

I believe the answer to this question is "it lets the compiler know what in the world is going on". The example given by the standard is

Code:

T::A* a7;

It sure looks like a declaration of a variable that points to T::A. Is T::A a type? Who knows! It could be a rather meaningless "multiply the variable T::A by a7" (meaningless in that the result isn't stored, but that's not illegal). It depends on what T is, so the compiler can't look it up to check. You have to soothe the compiler's anxiety by stating "this is a typename, really, I promise".

The default position appears to be something like "since variables appear 963 times more often in code than typenames, we'll assume it's a variable unless otherwise specified".

Originally Posted by tabstop

I believe the answer to this question is "it lets the compiler know what in the world is going on". The example given by the standard is

Code:

T::A* a7;

It sure looks like a declaration of a variable that points to T::A. Is T::A a type? Who knows! It could be a rather meaningless "multiply the variable T::A by a7" (meaningless in that the result isn't stored, but that's not illegal). It depends on what T is, so the compiler can't look it up to check. You have to soothe the compiler's anxiety by stating "this is a typename, really, I promise".

The default position appears to be something like "since variables appear 963 times more often in code than typenames, we'll assume it's a variable unless otherwise specified".

So the code for that declaration should actually be this?

Code:

typename T::A* a7;

As I said before, I've never dealt with templates. You can make it through most programming classes without ever touching templates or several other core concepts.

I'll chalk the sarcasm I'm hearing up to me needing sleep. Thanks for your help.