Critique my non-intrusive heap debugger

Question

This is a follow-up to Critique my heap debugger from yesterday. As suggested by bitc, I now keep metadata about the allocated blocks in a separate handwritten hashtable.

The heap debugger now detects the following kinds of errors:

1. memory leaks (now with more verbose debugging output)
2. illegal pointers passed to delete (that also takes care of double deletes)
3. wrong form of delete (array vs. non-array)
4. buffer overflows
5. buffer underflows

Feel free to discuss and thanks in advance!

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <new>

namespace
{
    // I don't want to #include <algorithm> for a single function template :)
    template <typename T>
    void my_swap(T& x, T& y)
    {
        T z(x);
        x = y;
        y = z;
    }

    typedef unsigned char byte;

    const byte CANARY[] = {0x5A, 0xFE, 0x6A, 0x8D,
                           0x5A, 0xFE, 0x6A, 0x8D,
                           0x5A, 0xFE, 0x6A, 0x8D,
                           0x5A, 0xFE, 0x6A, 0x8D};

    bool canary_dead(const byte* cage)
    {
        bool dead = memcmp(cage, CANARY, sizeof CANARY);
        if (dead)
        {
            for (size_t i = 0; i < sizeof CANARY; ++i)
            {
                byte b = cage[i];
                printf(b == CANARY[i] ? "__ " : "%2X ", b);
            }
            putchar('\n');
        }
        return dead;
    }

    enum kind_of_memory {AVAILABLE, TOMBSTONE, NON_ARRAY_MEMORY, ARRAY_MEMORY};

    const char* kind_string[] = {0, 0, "non-array memory", "    array memory"};

    struct metadata
    {
        byte* address;
        size_t size;
        kind_of_memory kind;

        bool in_use() const
        {
            return kind & 2;
        }

        void print() const
        {
            printf("%s at %p (%d bytes)\n", kind_string[kind], address, size);
        }

        bool must_keep_searching_for(void* address)
        {
            return kind == TOMBSTONE || (in_use() && address != this->address);
        }

        bool canaries_alive() const
        {
            bool alive = true;
            if (canary_dead(address - sizeof CANARY))
            {
                printf("ERROR:    buffer underflow at %p\n", address);
                alive = false;
            }
            if (canary_dead(address + size))
            {
                printf("ERROR:     buffer overflow at %p\n", address);
                alive = false;
            }
            return alive;
        }
    };

    const size_t MINIMUM_CAPACITY = 11;

    class hashtable
    {
        metadata* data;
        size_t used;
        size_t capacity;
        size_t tombstones;

    public:

        size_t size() const
        {
            return used - tombstones;
        }

        void print() const
        {
            for (size_t i = 0; i < capacity; ++i)
            {
                if (data[i].in_use())
                {
                    printf(":( leaked ");
                    data[i].print();
                }
            }
        }

        hashtable()
        {
            used = 0;
            capacity = MINIMUM_CAPACITY;
            data = static_cast<metadata*>(calloc(capacity, sizeof(metadata)));
            tombstones = 0;
        }

        ~hashtable()
        {
            free(data);
        }

        hashtable(const hashtable& that)
        {
            used = 0;
            capacity = 3 * that.size() | 1;
            if (capacity < MINIMUM_CAPACITY) capacity = MINIMUM_CAPACITY;
            data = static_cast<metadata*>(calloc(capacity, sizeof(metadata)));
            tombstones = 0;

            for (size_t i = 0; i < that.capacity; ++i)
            {
                if (that.data[i].in_use())
                {
                    insert_unsafe(that.data[i]);
                }
            }
        }

        hashtable& operator=(hashtable copy)
        {
            swap(copy);
            return *this;
        }

        void swap(hashtable& that)
        {
            my_swap(data, that.data);
            my_swap(used, that.used);
            my_swap(capacity, that.capacity);
            my_swap(tombstones, that.tombstones);
        }

        void insert_unsafe(const metadata& x)
        {
            *find(x.address) = x;
            ++used;
        }

        void insert(const metadata& x)
        {
            if (2 * used >= capacity)
            {
                hashtable copy(*this);
                swap(copy);
            }
            insert_unsafe(x);
        }

        metadata* find(void* address)
        {
            size_t index = reinterpret_cast<size_t>(address) % capacity;
            while (data[index].must_keep_searching_for(address))
            {
                ++index;
                if (index == capacity) index = 0;
            }
            return &data[index];
        }

        void erase(metadata* it)
        {
            it->kind = TOMBSTONE;
            ++tombstones;
        }
    } the_hashset;

    struct heap_debugger
    {
        heap_debugger()
        {
            puts("heap debugger started");
        }

        ~heap_debugger()
        {
            the_hashset.print();
            puts("heap debugger shutting down");
        }
    } the_heap_debugger;

    void* allocate(size_t size, kind_of_memory kind) throw (std::bad_alloc)
    {
        byte* raw = static_cast<byte*>(malloc(size + 2 * sizeof CANARY));
        if (raw == 0) throw std::bad_alloc();

        memcpy(raw, CANARY, sizeof CANARY);
        byte* payload = raw + sizeof CANARY;
        memcpy(payload + size, CANARY, sizeof CANARY);

        metadata md = {payload, size, kind};
        the_hashset.insert(md);
        printf("allocated ");
        md.print();
        return payload;
    }

    void release(void* payload, kind_of_memory kind) throw ()
    {
        if (payload == 0) return;

        metadata* p = the_hashset.find(payload);

        if (!p->in_use())
        {
            printf("ERROR:   no dynamic memory at %p\n", payload);
        }
        else if (p->kind != kind)
        {
            printf("ERROR:wrong form of delete at %p\n", payload);
        }
        else if (p->canaries_alive())
        {
            printf("releasing ");
            p->print();
            free(static_cast<byte*>(payload) - sizeof CANARY);
            the_hashset.erase(p);
        }
    }
}

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

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

void operator delete(void* payload) throw ()
{
    release(payload, NON_ARRAY_MEMORY);
}

void operator delete[](void* payload) throw ()
{
    release(payload, ARRAY_MEMORY);
}

int main()
{
    int* p = new int[1];
    delete p;   // wrong form of delete
    delete[] p; // ok
    delete p;   // no dynamic memory (double delete)

    p = new int[1];
    p[-1] = 0xcafebabe;
    p[+1] = 0x12345678;
    delete[] p; // underflow and overflow prevent release
                // p is not released, hence leak
}

Answer 1

Very nice, indeed. Your canaries could actually reveal some real cases of overflow/underflow (though not all of them as Matthieu pointed out).

What more. You might run into some problems with a multi-threaded application. Perhaps protect the hashtable from concurrent access?

Now that you log every allocation and deallocation, you can (if you like) provide more information about the program being tested. It might be interesting to know the total and average number of allocations at any given time? The total, max, min and average bytes allocated, and the average lifespan of allocations.

If you want to compare different threads, at least with Pthreads you can identify them with pthread_self(). This heap debugger could become a quite useful analysis tool.

Answer 2

Are you using a very weak malloc that doesn't already have this sort of stuff built into it? Because if it's there, you are doubling the overhead for little gain. Also, this kind of system really hurts when doing small object allocation or is ineffective with them as people do 1 alloc and manage the memory themselves.

As far as the code is concerned, it looks like it will do what you say it will do and it looks well designed and is easy to read. But, if you are going to go through the trouble of doing this though, why not catch your buffer over/under flows at the source by using managed containers/pointers/operator[] thingies. That way, you can debug on the spot of the failure instead of finding out at free that something evil has occured.

There are efficiencies to be had that I'm sure others will find, but these are just some thoughts off the top of my head after looking over your code for a few minutes.

Answer 3

I wonder about the detection of underflows / overflows.

I mean, if I have a 10 elements arrays, then it seems you'll detect if I write at -1 and 10, but what if I write at 20 ? Underflow or Overflow are not necessarily done as part of a buffer overrun (contiguous).

Furthermore, what's the point of preventing release of the block ? This block is (relatively) fine, it's the neighbors you've (unfortunately) corrupted.

Anyway, it seems pretty fine to me, though I would probably have more than one return per function because there's no point in Single Exit. You seem more of a C programmer than a C++ one :)