🚀 go-pugleaf

This post is along the lines of a MSL C++ usage tip.  This is a way to 
build a very simple memory debugger from some of the extensions found in 
MSL C++ (the Metrowerks implementation of the C++ standard library).

Although it can be built using earlier versions of CodeWarrior with some 
work, the article that follows takes advantage of some features of our 
latest CodeWarrior Development Studio for Mac, version 9 product (hint, 
hint, ;-) ).

So what is so special about a /very/ simple memory debugger?  Since it 
is so simple, it is easy to understand and adapt to your own needs.

What will it do for you?

   * It will detect whole program memory leaks.
   * It will detect "delete on new[]" or "delete[] on new" mismatch.
   * It will detect double deletes and non-heap based pointer deletes.
   * You can query it for how much memory is used at any point.
   * Because of the previous point, you can bracket a function call
     with usage queries to find out "memory leaked" for that call.
   * You can query a new-based pointer for how much memory it points to.
   * Performance is quite respectible for a memory debugger (but it is
     not intended for release code).

It is not thread safe.  But it is simple enough it easily could be made 
so.  Hmm... perhaps I'll write about the new Metrowerks::threads next. 
:-)

How does it work?

Overview
--------

Like most memory debuggers, it is based on overriding new and delete.  
This will not manage malloc/free.

The overridden new requests memory from malloc but before returning the 
pointer, registers it in a container with the requested size, and 
whether or not this is an array new.

The overridden delete looks up the pointer in the container.  If it 
can't find the pointer, it asserts.  Next it makes sure the "arrayness" 
of the pointer matches the "arrayness" of the delete.  If it doesn't, it 
asserts.  It then removes the pointer from the container before calling 
free.

At program end, if the container of pointers is not empty, the program 
asserts.

Details
-------

The first thing to realize is that the container that holds all of the 
pointer info better not use new/delete.  Else you would get into an 
infinite recursion situation.  The container must instead be based on 
malloc/free.  That way the container is not including its own heap usage 
in the statistics it collects.  The STL containers can be configured to 
use malloc/free instead of new/delete.  To do this you need a 
"mallocAllocator".

Below is a simple mallocAllocator:

// mallocAllocator.h

#ifndef mallocAllocator_h
#define mallocAllocator_h

#include <cstdlib>
#include <limits>
#include <new>
//#include <cassert>

template <class T>
class mallocAllocator;

template <>
class mallocAllocator<void>
{
public:
    typedef std::size_t    size_type;
    typedef std::ptrdiff_t difference_type;
    typedef void*          pointer;
    typedef const void*    const_pointer;
    typedef void           value_type;
    template <class U>
        struct rebind
        {
            typedef mallocAllocator<U> other;
        };
};

template <class T>
class mallocAllocator
{
public:
    typedef std::size_t    size_type;
    typedef std::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 mallocAllocator<U> other;
        };

    mallocAllocator() throw() {}
    template <class U> mallocAllocator(const mallocAllocator<U>&) 
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);
    void deallocate(pointer p, size_type) {std::free(p);}
    size_type max_size() const throw()
        {return std::numeric_limits<size_type>::max() / sizeof(T);}

    void construct(pointer p, const T& val) {::new((void*)p) T(val);}
    void destroy(pointer p)                 {p->~T();}
};

template <class T>
inline
typename mallocAllocator<T>::pointer
mallocAllocator<T>::allocate(size_type n, 
mallocAllocator<void>::const_pointer)
{
    pointer result = (pointer)std::malloc(n * sizeof(T));
    if (result == 0)
//        assert(false);
        throw std::bad_alloc();
    return result;
}

template <class T, class U>
inline
bool
operator==(const mallocAllocator<T>&, const mallocAllocator<U>&) throw()
{
    return true;
}

template <class T, class U>
inline
bool
operator!=(const mallocAllocator<T>&, const mallocAllocator<U>&) throw()
{
    return false;
}

#endif // mallocAllocator_h

This is the most simple allocator possible, and does nothing but call 
malloc/free instead of new/delete.  This one throws a std::bad_alloc if 
the heap is exhausted.  But if you prefer, you can have it assert 
instead.

The mallocAllocator is a general purpose tool and is presented here only 
because the memory debugger needs it.  Otherwise the mallocAllocator has 
nothing to do with memory debuggers.

Each pointer stored in the container must be mapped to a struct that 
stores the pointer's associated size, and "arrayness".  There are two 
containers in MSL C++ which are appropriate for this job:

std::map
Metrowerks::hash_map

I've chosen Metrowerks::hash_map for performance reasons.  The lookup 
time will be O(1) instead of O(log N).  The latest hash_map has a 
default hash function that will hash pointers (as well as all other 
scalars) which previous versions of our hash_map lack.

This information can be coded into a header, say simple_mem_debug.h like 
so:

// simple_mem_debug.h

#ifndef SIMPLE_MEM_DEBUG_H
#define SIMPLE_MEM_DEBUG_H

#include "mallocAllocator.h"
#include <hash_map>
#include <cstddef>

struct mem_info
{
    std::size_t size_;
    bool array_;
};

typedef Metrowerks::hash_map<void*, mem_info, Metrowerks::hash<void*>, 
                    std::equal_to<void*>,
                    mallocAllocator<std::pair<void*const, mem_info> > >
                    MemMap;

MemMap& get_memmap();

#endif  // SIMPLE_MEM_DEBUG_H

This header creates a struct mem_info to hold a size and an "arrayness" 
bool.  Then a typedef called MemMap is created which refers to a 
hash_map, mapping void* to mem_info, using the defaults for all other 
template parameters except for the allocator (which of course uses our 
mallocAllocator).

And a single function is prototyped:  get_memmap.  This is essentially 
the singleton pattern that will give clients access to the map of 
pointers.

So knowing that you have a hash_map<void*, mem_info, ...bla,bla>, and 
knowing that the user interface of hash_map is very, very close to 
std::map, you now know a great deal about how to use this debugger!  You 
can iterate over the container summing up pointer sizes.  And you can 
search this container for specific pointers and find out all about them 
(if they exist at all in the container).

We're not quite finished yet, but we're really not that far away either!  
There still needs to be a simple_mem_debug.cpp that implements 
everything we said we would do.  But it is only 113 lines long and 
presented below.

// simple_mem_debug.cpp

#include "simple_mem_debug.h"

#include <cassert>
#include <cstdlib>
#include <new>
#include <msl_utility>

First a nice sprinkling of includes.

void check_mem_leak()
{
    assert(get_memmap().empty());
}

MemMap& get_memmap()
{
    static bool init = false;
    static MemMap memmap;
    if (!init)
    {
        std::atexit(check_mem_leak);
        init = true;
    }
    return memmap;
}

get_memmap() has two jobs:

1.  Act as a singleton getter for the one instance of MemMap.
2.  Register the MemMap with atexit in such a way as to assert if the 
map isn't empty.

This second function is accomplished with check_mem_leak and is fairly 
self explanatory.  The atexit registration is done only the first time 
get_memmap is called thanks to the static init flag.

Next we need to implement the new and delete operators.  There are four 
new operators and four matching delete operators:  regular and nothrow 
crossed with non-array and array.  It is easiest to implement all of the 
logic in one function, and then forward the four variants to that 
function.

Here is the meat and potatoes for the new operators:

void* do_new(std::size_t size, bool is_array) throw(std::bad_alloc)
{
    if (size == 0)
        size = 1;
    Metrowerks::alloc_ptr<char, mallocAllocator<char> > ptr;
    while (true)
    {
        ptr.reset((char*)std::malloc(size));
        if (ptr.get() != 0)
            break;
        std::new_handler p = std::set_new_handler(0);
        std::set_new_handler(p);
        if (!p)
            throw std::bad_alloc();
        p();
    }
    mem_info& m = get_memmap()[ptr.get()];
    m.size_ = size;
    m.array_ = is_array;
    return ptr.release();
}

do_new takes a size requested, and whether or not this is for an array 
as parameters.  If the size is 0, it must be bumped to 1 (so says the 
C++ standard).  Next a little jewel from <msl_utility> comes into play:  
Metrowerks::alloc_ptr.  This is essentially a std::auto_ptr that can 
take an allocator for a deletion policy.  Use of this animal means we do 
not have to worry about exception safety while we store the pointer in 
the map.  If an exception is thrown, the alloc_ptr will clean up the 
allocated pointer using free.

The loop is standard fare for getting a pointer, and calling the new 
handler if the allocation doesn't succeed.  This is the type of logic 
that should go into any operator new.

After we get a pointer, then we get the memmap from the singleton 
function, store the pointer, and get a reference to the associated 
mem_info struct.  Then we simply fill in the struct with the parameters 
that were passed in.  And finally the alloc_ptr releases ownership of 
the pointer so that it can be returned to the client.

Now we just need the four operator new variants that will forward to 
do_new:

void* operator new (std::size_t size) throw(std::bad_alloc)
{
    return do_new(size, false);
}

void* operator new (std::size_t size, const std::nothrow_t&) throw()
{
    try
    {
        return operator new(size);
    }
    catch(...)
    {
    }
    return 0;
}

void* operator new [](std::size_t size) throw(std::bad_alloc)
{
    return do_new(size, true);
}

void* operator new [](std::size_t size, const std::nothrow_t&) throw()
{
    try
    {
        return operator new[](size);
    }
    catch(...)
    {
    }
    return 0;
}

The non-array versions pass in false, and the array versions pass in 
true.  The nothrow versions wrap the call with a try/catch and return 0 
on failure.

Next the delete logic:

void do_delete(void* ptr, bool is_array) throw()
{
    if (ptr)
    {
        MemMap& m = get_memmap();
        MemMap::iterator i = m.find(ptr);
        assert(i != m.end());
        assert(i->second.array_ == is_array);
        m.erase(i);
        std::free(ptr);
    }
}

If the pointer is non-null then we look it up in the memmap.  If it 
isn't there, assert.  If the arrayness of the pointer doesn't match the 
arrayness of the delete, assert.  Erase the pointer record from the 
memmap and free the pointer.

And the four variants of operator delete that forward to do_delete:

void operator delete (void* ptr) throw()
{
    do_delete(ptr, false);
}

void operator delete (void* ptr, const std::nothrow_t&) throw()
{
    operator delete(ptr);
}

void operator delete[](void* ptr) throw()
{
    do_delete(ptr, true);
}

void operator delete[](void* ptr, const std::nothrow_t&) throw()
{
    operator delete[](ptr);
}

And that is it!

As far as memory debug tools go, it just doesn't get any simpler than 
that.

Below is some HelloWorld type stuff to exercise our new toy:

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

std::size_t
memory_used()
{
    std::size_t result = 0;
    const MemMap& mem_debug = get_memmap();
    for (MemMap::const_iterator i = mem_debug.begin(),
                                e = mem_debug.end(); i != e; ++i)
        result += i->second.size_;
    return result;
};

#include <cassert>

std::size_t
memory_size(void* p)
{
    const MemMap& mem_debug = get_memmap();
    MemMap::const_iterator i = mem_debug.find(p);
    assert(i != mem_debug.end());
    return i->second.size_;
}

int main()
{
    std::cout << "memory used at point A: " << memory_used() << '\n';
    int* p1 = new int;
    std::cout << "memory used at point B: " << memory_used() << '\n';
    int* p2 = new int[10];
    std::cout << "memory used at point C: " << memory_used() << '\n';
    std::cout << "size of p2 is " << memory_size(p2) << '\n';
    delete p2;
    std::cout << "memory used at point D: " << memory_used() << '\n';
}

I've created a memory_used function which just loops over the memory map 
and adds up the sizes of all of the pointers.  And another utility 
memory_size that will return the size of a pointer given to it.  These 
aren't included in the simple_mem_debug utility because it is supposed 
to be ... well... simple!  You can probably dream up many more little 
helpers like this.  You might even add to the mem_info struct so that 
you can gather even more information, and add still more helpers taking 
advantage of that!

The above program (in PEF or Mach-O) prints out:

memory used at point A: 508
memory used at point B: 568
memory used at point C: 608
size of p2 is 40
Assertion (i->second.array_ == is_array) failed in 
"simple_mem_debug.cpp", function "do_delete", line 72

It is asserting because the delete p2 should read:

delete [] p2;

Fixing that bug the test now outputs:

memory used at point A: 508
memory used at point B: 568
memory used at point C: 608
size of p2 is 40
memory used at point D: 568
Assertion (get_memmap().empty()) failed in "simple_mem_debug.cpp", 
function "check_mem_leak", line 11

Hmm... leaked p1.

Add delete p1 right after delete [] p2:

memory used at point A: 508
memory used at point B: 568
memory used at point C: 608
size of p2 is 40
memory used at point D: 564

Everything looks good!

The reason you see 508 bytes in use at the start of main is because the 
iostreams (cout, cin, etc.) are being initialized before main, and they 
use new/delete.  Note, don't include <iostream> if you don't need it.  
There is a cost of simply including this header!

The reason 56 more bytes are in use at the end of main than at the 
beginning is again the iostream's fault.  As they are used, they further 
initialize themselves, using up more memory.  But that memory is cleaned 
up by the time our check_mem_leak() runs, else it would fire.  Yes, our 
little simple_mem_debug is even leak checking cout! :-)

It is rare that you can get so much power out of so little code.  I hope 
simple_mem_debug is as useful for you as it has been for me.

-Howard
The MSL C++ guy
Metrowerks