Valgrind: lettura non valida della dimensione 4 -> sigsegv, funziona bene senza valgrind e nello studio visivo

Question

Ho implementato un algoritmo di compressione (utilizzando la codifica huffman) che utilizza una coda di priorità dei nodi (una struttura definita). Ora, quando eseguo il codice solo in linux o in Visual Studio, tutto funziona correttamente. Quando controllo le perdite di memoria in Visual Studio, non ne viene dato nessuno.

Il problema ora è che quando uso valgrind per analizzare il mio programma, termina con il segnale 11 (sigsegv). Il primo errore riscontrato è una 'lettura non valida della dimensione 4' nel metodo delete min. Altri errori dopo sono: L'indirizzo è 0 byte in un blocco di dimensione 453 liberato, scrittura non valida di dimensione 4, non valido, cancella o realloc.

Qualcuno può darmi consigli su che tipo di errore avrei potuto fare? Ho cercato su Internet per ore, ma non riesco a trovare quello che sto facendo male (soprattutto perché funziona solo quando non si utilizza valgrind). O suggerimenti su come eseguire il debug e scoprire che cosa sta causando l'errore di lettura.

Grazie mille!

Ecco il codice nel caso in cui qualcuno volesse esaminarlo, ma suppongo che non sia così facile immergersi in questo specifico codice.

Sto indovinando che ha qualcosa a che fare con la coda di priorità del codice:

La parte in cui faccio la parte di Huffman -> ogni volta cancellare i 2 nodi minimali e aggiungere la somma di entrambi indietro come 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; 
} 

Ecco sono i metodi delete_min e insert_node per la coda di priorità:

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: Aggiunto l'output 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) 

Linea 331 è la linea in delete_min di: nodo * min = coda [0];

EDIT:

Il problema è risolto ora. Nella risposta accettata, il motivo per cui viene spiegato. Assegnando correttamente il valore riallocato, in delete_min sono stati risolti tutti i problemi.

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

Spiegherò il primo errore.

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

In linea 331, probabilmente la lettura di un int (unsigned), in una parte della memoria non si è assegnato per il proprio programma.

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

Questa parte fornisce ulteriori informazioni sulla parte di memoria che si è tentato di leggere. Dice che hai già usato la memoria, ma reallox l'ha liberata. Ciò significa che stai leggendo da un vecchio puntatore a una parte della memoria che hai già realizzato.

È necessario assicurarsi di utilizzare i ritorni di realloc del puntatore e non quello precedente.

Il motivo per cui questo non si arresta in modo anomalo durante l'esecuzione all'esterno di valgrind, è che la maggior parte delle volte la stessa parte di memoria verrà allocata da realloc. Quindi il puntatore rimane lo stesso, e come tale il tuo codice funzionerà. Tuttavia, a volte, realloc deciderà di spostare la parte della memoria, e quindi il tuo codice andrà in crash. Valgrind sta cercando di avvisarti per questo.

Gli altri errori verranno probabilmente risolti quando si utilizza il puntatore restituito.

Answer 2

In base agli errori Valgrind, probabilmente stai accedendo e liberando i nodi che hai già eliminato. Dovresti considerare di pubblicare gli errori Valgrind con i numeri di riga corrispondenti (compila con -g in gcc) per semplificare il nostro aiuto.

Modifica: L'errore più eclatante, il segfault, è dove è necessario iniziare il debug. Questa linea non riesce:

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

presumibilmente perché queue è nullo. Perché è NULL? Probabilmente perché realloc non ha assegnato nulla. Perché non ha assegnato nulla? O perché hai esaurito la memoria (improbabile) o perché hai tentato di allocare qualcosa della dimensione 0. (Vedi http://www.cplusplus.com/reference/cstdlib/realloc/ per i dettagli di realloc). Come hai potuto richiedere la taglia 0? Se p_queue->size-1 è 0.