Критику моего неинтрузивного отладчика кучи
Ниже приведена рекомендация Критика моего отладчика кучи со вчерашнего дня. Как было предложено bitc, теперь я храню метаданные о выделенных блоках в отдельной рукописной хэш-таблице.
Отладчик кучи теперь обнаруживает следующие виды ошибок:
- утечки памяти (теперь с более подробным результатом отладки)
- незаконные указатели, переданные для удаления (что также касается двойных удалений)
- неправильная форма удаления (массив против не-массива)
- переполнение буфера
- переполнение буфера
Не стесняйтесь обсуждать и благодарить заранее!
#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
}
Ответы
Ответ 1
Очень приятно. Ваши канарейки могут действительно выявить некоторые реальные случаи переполнения/недостаточного потока (хотя не все из них, как указал Маттиу).
Что еще. Вы можете столкнуться с некоторыми проблемами с многопоточным приложением. Возможно, защитите хэш-таблицу от одновременного доступа?
Теперь, когда вы регистрируете каждое распределение и освобождение, вы можете (если хотите) предоставить дополнительную информацию о тестируемой программе. Может быть интересно узнать общее и среднее количество распределений в любой момент времени? Вычисляются общие, максимальные, минимальные и средние байты и средний срок их выделения.
Если вы хотите сравнить разные потоки, по крайней мере с Pthreads, вы можете идентифицировать их с помощью pthread_self(). Этот отладчик кучи может стать весьма полезным инструментом анализа.
Ответ 2
Используете ли вы очень слабый malloc, у которого еще нет таких вещей, встроенных в него? Потому что, если он там, вы удваиваете накладные расходы для небольшого выигрыша. Кроме того, такая система действительно болит при выполнении небольшого размещения объектов или неэффективна с ними, поскольку люди делают 1 выделение и управление самой памятью.
Что касается кода, похоже, он будет делать то, что вы говорите, и будет выглядеть хорошо и легко читается. Но, если вы собираетесь решить эту проблему, почему бы не поймать ваш буфер поверх/под потоками в источнике, используя управляемые контейнеры/указатели/operator []. Таким образом, вы можете отлаживать на месте неудачи, а не обнаруживать на свободе, что произошло что-то злое.
Есть эффективность, которую я уверен, что другие найдут, но это всего лишь некоторые мысли с головы после того, как вы просмотрели свой код в течение нескольких минут.
Ответ 3
Интересно узнать об обнаружении переполнения/переполнения.
Я имею в виду, если у меня есть 10 массивов элементов, то, похоже, вы обнаружите, что я пишу в -1 и 10, но что, если я пишу в 20? Underflow или Overflow не обязательно выполняются как часть переполнения буфера (смежные).
Кроме того, какая точка предотвращения выпуска блока? Этот блок (относительно) прекрасен, это соседи, которые вы (к сожалению) испорчены.
Во всяком случае, мне кажется, что это очень хорошо, хотя у меня, вероятно, будет более одного возврата на каждую функцию, потому что нет смысла в Single Exit. Вы больше похожи программистом на C, чем на С++:)
