Блог

Я относительно новичок в программировании на C и в настоящее время работаю над простой хэш-таблицей (у меня есть опыт работы с другими языками).

Но теперь я столкнулся со странной проблемой памяти, и псевдо-решение, которое я нашел, еще более странное. Итак, у меня есть следующий код, который настраивает структуру моей хэш-таблицы:

 typedef struct HashTable {
    unsigned int size;
    TableEntry *table[];
} HashTable;

HashTable *create_table(unsigned int size) {
    HashTable *table = malloc(sizeof(unsigned int)   size*sizeof(TableEntry *)); 
    memset(table   sizeof(unsigned int), 0, size*sizeof(TableEntry *));       
    table->size = size;
    return table;
}
 

Я запустил этот код на двух машинах. На моем хост-компьютере с Windows это работает полностью нормально.
Но моя виртуальная машина Linux мне явно не нравится, потому что после вызова memset любой вызов malloc выдаст ошибку утверждения

 server: malloc.c:2401: sysmalloc: Assertion (old_top == initial_top (av) amp;amp; old_size == 0) || ((unsigned long) (old_size) >= MINSIZE amp;amp; prev_inuse (old_top) amp;amp; ((unsigned long) old_end amp; (pagesize - 1)) == 0) failed.
 

Я уже трачу часы, пытаясь выяснить, что вызывает здесь ошибку. Я полагаю, что это, вероятно, имеет какое-то отношение к вызову memset, но пока это мне не помогло. Я также использовал Valgrind, но это тоже не дало мне никакой новой информации.

Теперь начинается та часть, которая смущает меня больше всего. Второй malloc между вызовом malloc и memset каким-то образом устраняет проблему (пример приведен ниже). Даже если я выделяю 0 байт, он все равно работает нормально.

Итак, мое «исправление» выглядит примерно так:

 HashTable *create_table(unsigned int size) {
    HashTable *table = malloc(sizeof(unsigned int)   size*sizeof(TableEntry *)); 
    void *test = malloc(0); //this line
    memset(table   sizeof(unsigned int), 0, size*sizeof(TableEntry *));       
    table->size = size;
    return table;
} 
 

Теперь я был бы очень, очень благодарен, если бы кто-нибудь мог помочь мне выяснить

1. что вызывает ошибку
2. с какой стати второй вызов malloc исправляет это? Возможно, просто какие-то странные вещи на C, но мне все еще любопытно

«Какой-то чувак-программист» указал на ошибку, но есть более безопасный и более идиоматичный способ написать это.

Ваш подход по своей сути неверен, поскольку он предполагает, что элемент table массива HashTable начнется сразу после size элемента. Но это не обязательно верно; компилятор может вставить дополнение между ними. Действительно, в 64-разрядных системах это обычно имеет место, потому unsigned int что, вероятно, будет 4 байта, но ожидается, что указатели будут выровнены по 8-байтовой границе. Ваш текущий код также необходимо будет обновлять каждый раз, когда вы решите добавить или удалить участников из HashTable .

Таким образом, лучший подход заключается в следующем, используя тот факт, что sizeof применение к struct типу с гибким элементом массива вернет размер всего, что предшествует FAM, включая любое заполнение:

 HashTable *create_table(unsigned int size) {
    HashTable *table = malloc(sizeof(HashTable)   size*sizeof(TableEntry *)); 
    memset(table->table, 0, size*sizeof(TableEntry *));       
    table->size = size;
    return table;
}
 

Пара других возможных улучшений:

• при использовании sizeof многие люди предпочитают «разыменовывать» указатель, указывающий на нужный объект, а не называть его тип, поскольку это потенциально менее подвержено ошибкам.
• Размеры или длины массивов обычно следует использовать size_t вместо unsigned int . В 64-разрядной системе ваш текущий код не сможет обрабатывать хэш-таблицы размером более 4 ГБ, хотя система может поддерживать такие большие объекты просто отлично.
• Неудобно использовать имя table как для вашей локальной переменной create_table , так и для члена HashTable .
• Вы должны проверить, что malloc это удалось, прежде чем пытаться инициализировать выделенную память.

Я мог бы написать:

 #include <stdlib.h>
#include <string.h>
#include <stddef.h>

typedef struct HashTable {
    size_t size;
    TableEntry *entries[];
} HashTable;

HashTable *create_table(size_t size) {
    HashTable *table = malloc(sizeof(*table)   size*sizeof(table->entries[0]));
    if (!table) {
        // abort or return NULL
    }
    memset(table->entries, 0, size*sizeof(table->entries[0]));       
    table->size = size;
    return table;
}
 

Оставлено в качестве упражнения: правильно обработайте случай, когда параметр size настолько велик, что sizeof(*table) size*sizeof(table->entries[0]) переполняется size_t .

Помните, что арифметика указателя выполняется в базовой единице указателя, это то, что приводит к, например p[i] , точно так же, как *(p i) (для любого допустимого указателя или массива p и индекса i ).

Это означает, что ваше выражение table sizeof(unsigned int) будет таким же, как amp;table[sizeof(unsigned int)] , что, вероятно, не то, что вы ожидаете. Это, в свою очередь, приводит к тому, что ваш memset вызов выводит запись за пределы и приводит к неопределенному поведению.

Чтобы быть правильным, вам нужно привести указатель table к указателю char , как в (char *) table sizeof(unsigned int) .

Разница между ними заключается в добавленных смещениях байтов.

С помощью простого table sizeof(unsigned int) (без приведения) вы добавляете sizeof(HashTable) * sizeof(unsigned int) байты к указателю.

Когда вы приводите указатель, например, (char *) table sizeof(unsigned int) вы добавляете sizeof(char) * sizeof(unsigned int) байты к указателю.