c - valgrind options

Valgrind: lectura no válida de tamaño 4-> sigsegv, funciona bien sin valgrind y en visual studio

Question

He implementado un algoritmo de compresión (usando la codificación huffman) que usa una cola de prioridad de nodos (una estructura definida). Ahora, cuando ejecuto el código en Linux o en Visual Studio, todo funciona bien. Cuando compruebo que no haya fugas de memoria en Visual Studio, no se da ninguna.

El problema ahora es que cuando uso valgrind para analizar mi programa, termina con la señal 11 (sigsegv). El primer error encontrado es una ''lectura no válida de tamaño 4'' en el método delete min. Otros errores después de eso son: La dirección es 0 bytes dentro de un bloque de tamaño 453 liberado, escritura no válida de tamaño 4, libre inválido, eliminar o reasignar.

¿Alguien me puede aconsejar sobre qué tipo de error podría haber cometido? He estado buscando en Internet durante horas, pero no puedo encontrar lo que estoy haciendo mal (especialmente porque solo funciona cuando no uso valgrind). O consejos sobre cómo depurar y averiguar qué está causando el error de lectura.

¡Muchas gracias!

Aquí está el código en caso de que alguien quiera revisarlo, pero supongo que no es tan fácil simplemente sumergirse en este código específico.

Supongo que tiene algo que ver con la cola de prioridad del código:

La parte donde hago la parte huffman -> cada vez que elimino los 2 nodos mínimos y añado la suma de ambos como un nodo.

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

Aquí están los métodos delete_min y insert_node para la cola de prioridad:

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

EDITAR: Se agregó la salida de 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)

La línea 331 es la línea en delete_min de: node * min = queue [0];

EDITAR:

El problema está resuelto ahora. En la respuesta aceptada, se explica la razón por la cual. Simplemente asignando el valor reasignado correcto, en delete_min resolvió todos los problemas.

//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;

Answer 1

Según los errores de Valgrind, probablemente esté accediendo y liberando nodos que ya ha eliminado. Debe considerar la publicación de los errores de Valgrind con los números de línea correspondientes (compilar con -g en gcc) para que podamos ayudarlo más fácilmente.

Edición: el error más evidente, la falta de seguridad, es donde debe comenzar la depuración. Esta línea falla:

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

presumiblemente porque la queue es NULL. ¿Por qué es nulo? Probablemente porque el realloc no asignó nada. ¿Por qué no asignó nada? Ya sea porque se quedó sin memoria (improbable) o porque intentó asignar algo de tamaño 0. (Consulte http://www.cplusplus.com/reference/cstdlib/realloc/ para obtener más información sobre el realloc). ¿Cómo podrías solicitar talla 0? Si p_queue->size-1 es 0.

Answer 2

Te explicaré el primer error.

==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)

En la línea 331, es probable que estés leyendo un int (sin firma), en una parte de la memoria que no hayas asignado para tu propio programa.

==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==

Esta parte proporciona más información sobre la parte de la memoria que intentó leer. Dice que ya usaste la memoria, pero reallox la liberó. Eso significa que estás leyendo desde un puntero antiguo a una parte de la memoria que realmente te has liberado.

Debes asegurarte de usar el puntero realloc devuelve, y no el antiguo.

La razón por la que esto no se bloquea cuando se ejecuta fuera de valgrind es que, la mayoría de las veces, la misma parte de la memoria será asignada por realloc. Así que el puntero sigue siendo el mismo, y como tal su código funcionará. Sin embargo, a veces, realloc decidirá mover la parte de la memoria y luego su código se bloqueará. Valgrind está tratando de advertirte por esto.

El resto de los errores probablemente se resolverán cuando utilice el puntero devuelto.