Valgrind: ungültiges Lesen der Größe 4 -> Sigsegv, funktioniert ohne Valgrind und im Visual Studio

Question

Ich habe einen Komprimierungsalgorithmus (mit Huffman-Codierung) implementiert, die eine Prioritätswarteschlange von Knoten verwendet (eine Struktur definiert). Jetzt, wenn ich den Code nur in Linux oder im Visual Studio ausführe, funktioniert alles gut. Wenn ich im Visual Studio nach Speicherlecks suche, werden keine angegeben.

Das Problem ist jetzt, wenn ich valgrind, um mein Programm zu analysieren, es endet mit Signal 11 (Sigsegv). Der erste gefundene Fehler ist ein 'ungültiger Lesewert der Größe 4' in der Methode delete min. Andere Fehler danach sind: Adresse ist 0 Bytes in einem Block der Größe 453 freigegeben, ungültiger Schreibvorgang der Größe 4, ungültig frei, löschen oder Realloc.

Kann mir jemand Auskunft geben, welche Art von Fehler ich möglicherweise hätte machen können? Ich habe stundenlang im Internet gesucht, kann aber nicht finden, was ich falsch mache (besonders, weil es einfach funktioniert, wenn man nicht valgrind verwendet). Oder Tipps zum Debuggen und Finden, was den Lesefehler verursacht.

Vielen Dank!

Hier ist der Code für den Fall, dass jemand es überprüfen möchte, aber ich denke, dass es nicht so einfach ist, in diesem speziellen Code zu tauchen.

Ich vermute, es hat etwas mit der Prioritätswarteschlange des Codes zu tun:

Der Teil, wo ich den Huffman Teil tun -> jedes Mal die 2 minimale Knoten löschen und die Summe beider hinzufügen zurück ein Knoten.

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

sind ist hier die delete_min und insert_node Methoden für die Prioritäts-Warteschlange:

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: Hinzugefügt die valgrind Ausgang:

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) 

Zeile 331 ist die Linie, in delete_min von: Knoten * min = Warteschlange [0];

EDIT:

Das Problem ist jetzt gelöst. In der angenommenen Antwort wird der Grund erklärt. Einfach den realloced Wert korrekt zuweisen, löschte in delete_min alle Probleme.

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

Ich erkläre Ihnen den ersten Fehler.

==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 Zeile 331, sind Sie wahrscheinlich ein (unsigned) int, in einem Teil des Speichers Lesen Sie für Ihr eigenes Programm nicht zugeordnet werden.

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

Dieser Teil enthält weitere Informationen zu dem Teil des Speichers, den Sie zu lesen versucht haben. Es besagt, dass Sie bereits den Speicher verwendet haben, aber reallox hat ihn freigegeben. Das bedeutet, dass Sie von einem alten Zeiger auf einen Teil des Speichers lesen, den Sie neu zugewiesen haben.

Sie sollten sicherstellen, dass Sie den Zeiger Realloc zurückgibt, und nicht den alten.

Der Grund dafür, dass dies nicht beim Absturz beim Ausführen von Valgrind abstürzt, ist, dass der gleiche Teil des Speichers meistens von realloc zugewiesen wird. Der Zeiger bleibt also gleich und Ihr Code wird funktionieren. Manchmal wird realloc jedoch entscheiden, den Teil des Speichers zu verschieben, und dann stürzt Ihr Code ab. Valgrind versucht dich davor zu warnen.

Der Rest der Fehler wird wahrscheinlich gelöst, wenn Sie den zurückgegebenen Zeiger verwenden.

Answer 2

Basierend auf Ihren Valgrind-Fehlern greifen Sie wahrscheinlich auf Knoten zu, die Sie bereits gelöscht haben, und geben diese frei. Sie sollten die Valgrind-Fehler mit den entsprechenden Zeilennummern posten (kompilieren Sie mit -g in gcc), damit wir Ihnen leichter helfen können.

Edit: Der grellste Fehler, der segfault, ist, wo Sie mit dem Debuggen beginnen sollten. Diese Linie versagt:

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

vermutlich weil queue NULL ist. Warum ist es NULL? Wahrscheinlich, weil realloc nichts zugewiesen hat. Warum hat es nichts zugeteilt? Entweder, weil Ihnen der Speicher ausgegangen ist (unwahrscheinlich) oder weil Sie versucht haben, etwas mit der Größe 0 zuzuweisen. (Einzelheiten zur Neuzuordnung finden Sie unter http://www.cplusplus.com/reference/cstdlib/realloc/). Wie können Sie Größe 0 anfordern? Wenn p_queue->size-1 0 ist.