問題描述

這是對昨天的批評我的堆調(diào)試器的后續(xù).按照 bitc 的建議，我現(xiàn)在將有關(guān)已分配塊的元數(shù)據(jù)保存在單獨(dú)的手寫哈希表中.

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.

堆調(diào)試器現(xiàn)在檢測以下類型的錯誤:

The heap debugger now detects the following kinds of errors:

1. 內(nèi)存泄漏(現(xiàn)在有更詳細(xì)的調(diào)試輸出)
2. 傳遞給 delete 的非法指針(也處理雙重刪除)
3. 錯誤的刪除形式(數(shù)組與非數(shù)組)
4. 緩沖區(qū)溢出
5. 緩沖區(qū)下溢

歡迎討論并提前致謝！

#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
}

推薦答案

非常好，確實(shí).您的金絲雀實(shí)際上可以揭示一些真實(shí)的上溢/下溢情況(盡管不是馬修指出的所有情況).

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

還有什么.您可能會遇到多線程應(yīng)用程序的一些問題.也許可以保護(hù)哈希表免受并發(fā)訪問?

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

既然您記錄了每個分配和解除分配，您可以(如果愿意)提供有關(guān)正在測試的程序的更多信息.了解任何給定時間的總分配數(shù)和平均分配數(shù)可能會很有趣?分配的總字節(jié)數(shù)、最大字節(jié)數(shù)、最小字節(jié)數(shù)和平均字節(jié)數(shù)，以及分配的平均壽命.

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.

如果你想比較不同的線程，至少在 Pthreads 中你可以用 pthread_self() 來識別它們.這個堆調(diào)試器可以成為一個非常有用的分析工具.

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.

這篇關(guān)于批評我的非侵入式堆調(diào)試器的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網(wǎng)！