c++ - 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('
');
        }
        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)
", 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
", address);
                alive = false;
            }
            if (canary_dead(address + size))
            {
                printf("ERROR:     buffer overflow at %p
", 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
", payload);
        }
        else if (p->kind != kind)
        {
            printf("ERROR:wrong form of delete at %p
", 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.