Valgrind: ongeldige lezing van maat 4 -> sigsegv, werkt prima zonder valgrind en in visuele studio

Ik heb een compressie-algoritme geïmplementeerd (met behulp van huffman-codering) dat een prioriteitswachtrij van knooppunten gebruikt (een struct die ik heb gedefinieerd). Nu, wanneer ik de code gewoon in linux of in visuele studio uitvoer, werkt alles prima. Als ik in Visual Studio op geheugenlekken controleer, wordt er geen gegeven.

Het probleem is nu dat als ik valgrind gebruik om mijn programma te analyseren, het eindigt met signaal 11 (sigsegv). De eerste fout die wordt aangetroffen is een ‘invalid read of size 4’ in de methode delete min. Andere fouten daarna zijn: Adres is 0 bytes binnen een blok van grootte 453 bevrijd, ongeldig schrijven van grootte 4, ongeldig vrij, verwijderen of opnieuw plaatsen.

Kan iemand mij advies geven over wat voor soort fout ik zou kunnen hebben gemaakt? Ik heb uren op internet gezocht, maar kan niet vinden wat ik verkeerd doe (vooral omdat het gewoon werkt als ik valgrind niet gebruik). Of tips om fouten op te sporen en erachter te komen wat de leesfout veroorzaakt.

Hartelijk dank!

Hier is de code voor het geval iemand hem wil nakijken, maar ik denk dat het niet zo eenvoudig is om zomaar in deze specifieke code te duiken.

Ik vermoed dat het iets te maken heeft met de prioriteitswachtrij van de code:

Het gedeelte waar ik het huffman-gedeelte doe -> verwijder elke keer de 2 minimale knooppunten en tel de som van beide weer op als één knooppunt.

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

Hier zijn de delete_min en insert_node methoden voor de prioriteitswachtrij:

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-uitvoer toegevoegd:

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)

Regel 331 is de regel in delete_min van: node* min = wachtrij[0];

BEWERKEN:

Het probleem is nu opgelost. In het geaccepteerde antwoord wordt de reden uitgelegd. Gewoon de opnieuw toegewezen waarde correct toewijzen, in delete_min losten alle problemen op.

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

Antwoord 1, autoriteit 100%

Ik zal je de eerste fout uitleggen.

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

Op regel 331 lees je waarschijnlijk een (niet ondertekende) int, in een deel van het geheugen dat je niet hebt toegewezen aan je eigen 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==

Dit deel geeft meer informatie over het deel van het geheugen dat je probeerde te lezen. Er staat dat je het geheugen al hebt gebruikt, maar reallox heeft het vrijgemaakt. Dat betekent dat je leest van een oude aanwijzer naar een deel van het geheugen dat je opnieuw hebt toegewezen.

Je moet ervoor zorgen dat je de pointer realloc returns gebruikt, en niet de oude.

De reden dat dit niet crasht als je buiten valgrind draait, is dat meestal hetzelfde deel van het geheugen wordt toegewezen door realloc. Dus de aanwijzer blijft hetzelfde, en als zodanig zal uw code werken. Soms besluit realloc echter om het deel van het geheugen te verplaatsen, en dan crasht je code. Valgrind probeert je hiervoor te waarschuwen.

De rest van de fouten zullen waarschijnlijk worden opgelost wanneer u de geretourneerde aanwijzer gebruikt.


Antwoord 2, autoriteit 11%

Op basis van je Valgrind-fouten ben je waarschijnlijk bezig met het openen en vrijgeven van nodes die je al hebt verwijderd. Overweeg om de Valgrind-fouten met de bijbehorende regelnummers te posten (compileer met -g in gcc) om het voor ons gemakkelijker te maken om u te helpen.

Bewerken: de meest in het oog springende fout, de segfault, is waar je moet beginnen met debuggen. Deze regel mislukt:

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

vermoedelijk omdat queueNULL is. Waarom is het NULL? Waarschijnlijk omdat realloc niets heeft toegewezen. Waarom heeft het niets toegewezen? Ofwel omdat je geen geheugen meer had (onwaarschijnlijk) of omdat je probeerde iets van grootte 0 toe te wijzen. (Zie http://www.cplusplus.com/reference/cstdlib/realloc/voor details over realloc). Hoe kunt u maat 0 aanvragen? Als p_queue->size-10 is.

Other episodes