Подтвердить что ты не робот

Valgrind: недопустимое чтение размером 4 → sigsegv, отлично работает без valgrind и в visual studio

Я реализовал алгоритм сжатия (с использованием кодирования хаффмана), который использует приоритетную очередь узлов (определенная структура i). Теперь, когда я просто запускаю код в linux или в visual studio, все работает нормально. Когда я проверяю утечку памяти в визуальной студии, ничего не дается.

Проблема заключается в том, что когда я использую valgrind для анализа моей программы, она заканчивается сигналом 11 (sigsegv). Первой ошибкой является "недопустимое чтение размера 4" в методе delete min. Другие ошибки после этого: Адрес - 0 байтов в блоке размером 453, освобожденном, недействительной записи размера 4, недопустимом свободном, удалении или realloc.

Может ли кто-нибудь дать мне совет о том, какую ошибку я мог бы сделать? Я много часов ищу в Интернете, но не могу найти, что я делаю неправильно (особенно потому, что он работает, когда не используется valgrind). Или подскажите, как отлаживать и выяснить, что вызывает ошибку чтения.

Большое спасибо!

Вот код, если кто-то захочет его просмотреть, но я думаю, что не так просто просто погрузиться в этот конкретный код.

Я предполагаю, что это имеет какое-то отношение к очереди приоритетов кода:

Часть, где я делаю часть хаффмана → каждый раз, удаляя два минимальных узла и добавляя сумму обратно как один node.

while(queue->size > 1){
    node* n1 = delete_min(queue);
    node* n2 = delete_min(queue); // all the errors are encountered in this call
    node* temp = (node*) calloc(sizeof(node),1);
    temp->amount = n1->amount + n2->amount;
    insert_node(queue,temp);
    n1->parent = temp;
    n2->parent = temp;
    temp->left = n1;
    temp->right = n2;
}

Вот методы delete_min и insert_node для очереди приоритетов:

void insert_node(priority_queue* p_queue, node* x){
    int i = p_queue->size;
    if(i == 0){
        p_queue->queue = (node**) malloc(sizeof(node*));
    }
    else{
        p_queue->queue = (node**) realloc(p_queue->queue,sizeof(node*)*(p_queue->size+1));
    }
    p_queue->queue[p_queue->size] = x;

    while(i>=0 && p_queue->queue[i]->amount < p_queue->queue[(i-1)/2]->amount){
        node* temp = p_queue->queue[i];
        p_queue->queue[i] = p_queue->queue[(i-1)/2];
        p_queue->queue[(i-1)/2] = temp;
        i = (i-1)/2;
    }
    p_queue->size++;
}

node* delete_min(priority_queue* p_queue){
    node** queue = p_queue->queue;
    node* min = queue[0];

    if(p_queue->size>1){
        int r = 0;
        int current = 1; //left child of root

        queue[0] = queue[p_queue->size-1];
        queue = (node**) realloc(queue,sizeof(node*)*(--p_queue->size));
        while(current < p_queue->size){
            //in case of 2 children, check if current needs to be right or left child
            if(current < p_queue->size-1 && queue[current] > queue[current+1]){
                current++;
            } 
            if(queue[current] < queue[r]){
                node* temp = queue[r];
                queue[r] = queue[current];
                queue[current] = temp;

                r = current;
                current = 2 * current;
            }
            else{
                break;
            }
            current++;
        }
    }
    else{
        free(queue);
        p_queue->size--;
    }
    return min;
}

EDIT: добавлен вывод valgrind:

Invalid read of size 4
==1893==    at 0x80498E0: delete_min (huffman.c:331)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid read of size 4
==1893==    at 0x8049901: delete_min (huffman.c:333)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441db64 is 444 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid write of size 4
==1893==    at 0x8049906: delete_min (huffman.c:333)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid free() / delete / delete[] / realloc()
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid read of size 4
==1893==    at 0x8049A0E: delete_min (huffman.c:337)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==1893== 
==1893== 
==1893== Process terminating with default action of signal 11 (SIGSEGV)
==1893==  Access not within mapped region at address 0x0
==1893==    at 0x8049A0E: delete_min (huffman.c:337)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)

Строка 331 - это строка в delete_min из: node * min = queue [0];

EDIT:

Теперь проблема решена. В принятом ответе объясняется причина. Просто назначив правильное значение realloced, в delete_min решили все проблемы.

//realloc queue and assign new value to local queue var
p_queue->queue = (node**) realloc(queue,sizeof(node*)*(--p_queue->grootte));
queue = p_queue->queue;
4b9b3361

ОТВЕТЫ

Ответ 1

Я объясню вам первую ошибку.

==1893== Invalid read of size 4
==1893==    at 0x80498E0: delete_min (huffman.c:331)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)

В строке 331 вы, вероятно, читаете (без знака) int в части памяти, которую вы не выделили для своей собственной программы.

==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==

В этой части содержится дополнительная информация о той части памяти, которую вы пытались прочитать. В нем говорится, что вы уже использовали память, но reallox освободил ее. Это означает, что вы читаете старый указатель на часть памяти, которую вы перераспределили.

Вы должны убедиться, что используете realloc указателя, а не старый.

Причина, по которой это не сбой при работе вне valgrind, заключается в том, что большую часть времени одна и та же часть памяти будет выделена realloc. Таким образом, указатель остается тем же, и как таковой ваш код будет работать. Однако иногда realloc решит переместить часть памяти, а затем ваш код сработает. Valgrind пытается предупредить вас об этом.

Остальные ошибки, вероятно, будут решены, если вы используете возвращаемый указатель.

Ответ 2

Основываясь на ваших ошибках Valgrind, вы, вероятно, получаете доступ, а затем освобождаете узлы, которые вы уже удалили. Вы должны рассмотреть возможность размещения ошибок Valgrind с соответствующими номерами строк (скомпилировать с -g в gcc), чтобы облегчить нам помощь.

Изменить: наиболее вопиющая ошибка, segfault, - это то, где вы должны начать отладку. Эта строка не работает:

while((2*i)+2 < p_queue->grootte-1 && (queue[i]->amount > queue[(2*i)+1]->amount || queue[i]->amount > queue[(2*i)+2]->amount)){

предположительно, потому что queue имеет значение NULL. Почему это NULL? Возможно, потому что realloc ничего не выделял. Почему он ничего не выделял? Либо потому, что у вас закончилась нехватка памяти (маловероятно), либо потому, что вы попытались выделить что-то размером 0. (Подробнее о realloc см. http://www.cplusplus.com/reference/cstdlib/realloc/), Как вы можете запросить размер 0? Если p_queue->size-1 равно 0.