[C++] Random crashes bij delete[]

[Knakker]

Kan iemand deze toegepast-wiskundige-in-nood helpen?

Ik ben een algoritme aan het implementeren in C++ (gebruik Dev-C++). Ik heb last van random crashes bij gebruik van het delete[]-statement. Ik heb al gezocht en dit kan een aantal oorzaken hebben; ik ben alleen niet in staat om mijn fout te vinden!

Idee achter dit stukje code is dat een twee cycles in een logistiek netwerk in één 'gepatcht' worden. Het probleem doet zich soms voor bij het delete[] statement in het midden, en soms op het eind. Soms ook niet.

Alvast bedankt!

Patch[0] en Patch[1] zijn niets anders anders de verwijzingen naar de desbetreffende cycles. Cycles[..][0] geeft de lengte van de cycle aan; de array moet dus Cycles[..][0]+1 groot zijn.

C++:

void PatchCycles (int **Cycles, int &CycleCount, int *Patch) {
    int I, J;
      
    // Theoretisch is de plus 1 niet nodig, maar goed, voor de zekerheid
    Cycles[CycleCount+1] = new int[ Cycles[Patch[0]][0] + Cycles[Patch[1]][0] + 1 ];

    // Cycle-patching gebeurd hier; nieuwe cycle wordt in Cycles[CycleCount+1] gegooid.
    // Array Cycles is groot genoeg (voor de zekerheid supergroot gemaakt om te checken)
    
    // Now replace the cycle with the lowest index by the cycle just created
    int Lowest, Highest;
    if (Patch[0] < Patch[1]) { Lowest = Patch[0]; Highest = Patch[1]; }
    if (Patch[0] > Patch[1]) { Lowest = Patch[1]; Highest = Patch[0]; }
   
    // Redefine the array with the lowest index ...
    delete[] Cycles[Lowest]; 
    Cycles[Lowest] = new int[Cycles[CycleCount+1][0]+1];

    // ... and copy the contents of the newly generated cycle
    for (I = 0; I <= Cycles[CycleCount+1][0]; I++) {
        Cycles[Lowest][I] = Cycles[CycleCount+1][I];
        }
    // Move all arrays with an index higher than Highest one down
    if (Highest < CycleCount) {
       for (I = Highest; I < CycleCount; I++) {      
           delete[] Cycles[I];
           Cycles[I] = new int[Cycles[I+1][0]+1];
           for (J = 0; J <= Cycles[I+1][0]; J++) {
               Cycles[I][J] = Cycles[I+1][J];
               }
           }
       }

    // Delete the two highest
    delete[] Cycles[CycleCount]; 
    delete[] Cycles[CycleCount+1]; 
    CycleCount--;
    printf("Patching complete.\n");
    }

[ Voor 12% gewijzigd door moto-moi op 02-11-2005 00:11 . Reden: even de syntaxhighlighting aangezet :) ]

[H!GHGuY]

schrijf eens het geheugen adres uit waarop je de delete uitvoert, en zet de pointer ook op NULL nadat je hebt gedelete.

als je kan, ga het eens met een debugger te lijf, dingen zoals dit zijn dan een piece of cake om uit te zoeken.

[Rowwan]

Ik heb je code niet helemaal gelezen (ontwikkelaars zijn lui ) maar als ik zo even door je code scan zie ik nogal wat gerommel met de cyclecount. Bij regel 5 wordt er 1 bij opgeteld (voor de zekerheid:?)

Volgens mij bestaat Cycles[0] dus niet. Toch kun je deze verwijderen in regel 35.

[.oisyn]

Tja, dit is toch echt typisch debug-werk, en met een niet zo simpele functie als jij daar hebt waar we bovendien niet van weten hoe hij aangeroepen gaat worden kunnen we je toch vrij moeilijk helpen

Waarschijnlijk schrijf je buiten de gealloceerde buffer of probeer je meerdere keren dezelfde pointer te verwijderen. Beide gevallen kunnen leiden tot heap corruption en dus een crash bij een willekeurige allocatie of deallocatie.

Er bestaat software om dit soort dingen te detecteren (Rational Purify, Boundschecker, ...), maar het is ook vrij makkelijk zelf te doen: maak een allocatie en deallocatie functie, en roep die aan in je algoritme ipv new en delete. In die functies alloceer je het geheugen en stop je de verkregen pointers in een container (een std::set lijkt me hier de beste keuze). Bij verwijderen controleer je of de pointer in die container staat alvorens je 'm delete. Als dat niet het geval is dan probeer je dus óf een stuk geheugen te dealloceren wat je helemaal niet gealloceerd hebt, óf je dealloceerd hetzelfde stuk geheugen meer dan eens.

[Knakker]

Er bestaat software om dit soort dingen te detecteren (Rational Purify, Boundschecker, ...), maar het is ook vrij makkelijk zelf te doen: maak een allocatie en deallocatie functie, en roep die aan in je algoritme ipv new en delete. In die functies alloceer je het geheugen en stop je de verkregen pointers in een container (een std::set lijkt me hier de beste keuze). Bij verwijderen controleer je of de pointer in die container staat alvorens je 'm delete. Als dat niet het geval is dan probeer je dus óf een stuk geheugen te dealloceren wat je helemaal niet gealloceerd hebt, óf je dealloceerd hetzelfde stuk geheugen meer dan eens.

Dit zal ik in ieder geval proberen! Ik moet de functie toch verder uitbreiden dus ik heb besloten maar een nieuwe 'from scratch' te maken (dit is niet zo ingewikkeld) waarbij ik zo secuur mogelijk te werk ga.

In ieder geval bedankt voor de respons!

[MSalters]

'k Zou gewoon een eigen new en delete maken, waarom nieuwe namen verzinnen? Dan hoef je ook geen bestaande code aan te passen.

Nog beter idee: helemaal geen new[]/delete[] gebruiken. Er is maar 1 goede reden voor die functies, en dat is om een container class te schrijven zoals std::vector<>. Die bestaat al, dus verder die gebruiken.

[Knakker]

Ik heb alles herschreven, maar had te maken met een énorme memory leak (ongeveer 8 MB aan extra geheugen per iteratie). Daarom heb ik de array die vaak van dimensie verandert vervangen door een vector; werkt fantastisch, dit had ik eerder moeten weten

Ik heb alleen te maken met een kleine memory-leak per iteratie, van 64 kB. Hoe komt dit? Dit is de relevante code:

code:

    // De manier waarop PatchCosts wordt gedeclareerd
    vector < vector<int> > **PatchCosts;
    PatchCosts = new vector < vector<int> >*[CycleTotal+1];
    for (I = 0; I < CycleTotal; I++) {
        PatchCosts[I] = new vector < vector<int> >[CycleTotal+1];
        }

    // Hier gebeurt een hoop

    while (CycleCount > 1) { 

        // hier gebeurt nog meer

        PatchCosts[C1][C2].clear();
        PatchCosts[C1][C2].resize(Cycles[C1][0]-1);

        for (K = 1; K < Cycles[C1][0]; K++) {
            for (L = 1; L < Cycles[C2][0]; L++) {
                // Cost = hele ingewikkelde berekening
                PatchCosts[C1][C2][K-1].push_back(Cost);
                }
            }        
        
        // hier gebeurt nog veel meer

        CycleCount--;
        }

[ Voor 17% gewijzigd door Knakker op 06-11-2005 18:04 ]

[Soultaker]

Klopt het trouwens dat PatchCost een vector<vector<vector<int> > > is? Hoe meet je dit geheugenverlies precies?

In je code zie ik geen fouten staan, maar als je je vectors steeds groter maakt ga je natuurlijk steeds meer geheugen gebruiken.

edit:
In jouw geëditte post alloceer je trouwens CycleTotal+1 pointers en vervolgens alloceer je er maar CycleTotal. Dat is natuurlijk wat vreemd. Verder mis ik de code om die gealloceerde vectors weer vrij te geven, maar ik neem aan dat je met 'iteraties' de code vanaf regel 10 bedoelt en het geheugen dat je daarvoor alloceert toch al niet meerekent?

[ Voor 46% gewijzigd door Soultaker op 06-11-2005 18:09 ]

[Knakker]

Klopt het trouwens dat PatchCost een vector<vector<vector<int> > > is? Hoe meet je dit geheugenverlies precies?

Om eerlijk te zijn heb ik geen idee welke vorm PatchCosts heeft. Ik weet dat mijn vragen wellicht wat vervelend over kunnen komen, ik ben nou eenmaal geen programmeur , sorry alvast: advies is welkom!

Ik heb te maken met N cycles; elke cycle bevat M arcs, waarbij M varieert van cycle tot cycle.

PatchCosts[I][J][K][L] geeft aan hoe groot de kosten zijn om cycles I en J te 'patchen' (tot één cycle te maken) door arc K uit cycle I en arc L uit cycle J te verwijderen. De kost zelf moet een integer zijn.

Ik houd er rekening mee dat PatchCosts[I][J][K][L] identiek is aan PatchCosts[J][I][L][K]; ik bereken maar één van beiden. Indicator I loopt van 0 tot CycleTotal en indicator J van I+1 tot en met CycleTotal (er ontstaat dus een soort bovendriehoeksmatrix). De array is op dit moment dus te groot (de eerste twee dimensies zijn CycleTotal+1 bij CycleTotal+1 terwijl dat niet nodig is), maar goed - dat komt later wel.

Het meten doe ik op de "Harry"-manier: gewoon in Windows-taakbeheer kijken Het viel me op dat bij iedere iteratie er precies 64kB bij kwam.

In je code zie ik geen fouten staan, maar als je je vectors steeds groter maakt ga je natuurlijk steeds meer geheugen gebruiken.

De gedachte erachter is dat geheugengebruik constant moet zijn (ik vermaak twee cycles van lengte M1 en M2 tot één van lengte M1+M2), maar ik bedenk me net dat ik [C2][C2+1...CycleTotal] helemaal niet vrijgeef... duh

In jouw geëditte post alloceer je trouwens CycleTotal+1 pointers en vervolgens alloceer je er maar CycleTotal. Dat is natuurlijk wat vreemd. Verder mis ik de code om die gealloceerde vectors weer vrij te geven, maar ik neem aan dat je met 'iteraties' de code vanaf regel 10 bedoelt en het geheugen dat je daarvoor alloceert toch al niet meerekent?

Ik 'mat' alleen het verschil in geheugengebruik tussen elke iteratie (inderdaad de while-loop). Dit is alleen de code die betrekking had op het 'resizen' van de vectoren. Uiteraard worden alle arrays die op de heap gealloceerd worden wel vrijgegeven op het einde.

[ Voor 3% gewijzigd door Knakker op 06-11-2005 18:35 ]

[Soultaker]

Mja, geheugenallocatie is nogal grillig, en een paar kilobyte meer in Windows' taakbeheer zegt niets. Zonder aparte tools te gebruiken kun je het beste nog het hele algoritme een stuk of duizend keer uitvoeren en dan kijken of je meer geheugen gealloceert hebt.

Als je onder Windows werkt, welke compiler/IDE gebruik je dan? Microsoft's C++ compiler (of eigenlijk de debug CRT library) heeft geïntegreerde leakchecking die je kunt gebruiken om objectief vast te stellen óf er geheugen wordt gelekt en ook om een indicatie te krijgen wáár dat gebeurt).

Zie bijvoorbeeld:
http://msdn.microsoft.com...gIsolatingMemoryLeaks.asp

Zoals ik al zei: je code zelf is niet fout en veroorzaakt geen leaks, indien je:
• de met new gealloceerde objecten vrijgeeft;
• en geen heap corruption veroorzaakt door buiten de grenzen van de vectors te schrijven of iets dergelijks (dit kan de Microsoft CRT ook checken).
Punt 1 staat niet in je code maar je zegt dat je er voor gezorgd hebt. Van punt 2 lijkt mij ook geen sprake, voor zover ik dat kan beoordelen a.d.h.v. de code die je post.

[ Voor 11% gewijzigd door Soultaker op 06-11-2005 18:52 ]

[Knakker]

Binnenkort neem ik mijn code op in een test-procedure waar ik het ongeveer 1000 keer achter elkaar uitvoer op allerlei verschillende instanties; dan merk ik gauw genoeg of er sprake is van een memory-leak...

In ieder geval bedankt voor de hulp, en ik hoop dat ik vanaf nu niets meer nodig heb!