Memory Leak bei STD::Map



  • Hy @ all,
    ich habe ein sehr seltsames Problem. Da meines Erachtens nach es leider in der STL keine HashMap gibt, hab ich mich mal daran versucht eine ganz simple Hashmap zu schreiben.
    Soweit bin ich bis jetzt:

    stringutils.hh

    #ifndef stringutils_hpp
        #define stringutils_hpp
    
        #include <string.h>
        #include <string>
        #include <iostream>
        #include <sstream>
    
        namespace stringutils{
          using namespace std;
          /**
             hashSDBM
             wandelt char* in Hashwert (SDBM - Algorithmus)
             @param strToHash            zu hashender String
             @return Hashwert
          */
          unsigned long& hashSDBM(char *strToHash){
              static unsigned long hash;
              hash = 0;          
              unsigned char* str = new unsigned char[strlen(strToHash) + 1];
              strncpy( (char *) str, strToHash, strlen(strToHash) );
    
              int i = 0;
    
              while(str[i]){
                hash = str[i] + (hash <<6) + (hash <<16) - hash;
                ++i;
              }
              delete [] str;
    
              return (hash);
          }
        }
    
    #endif
    

    Die Funktion HashSDBM soll eigentlich nichts weiter tun, als einen string zu hashen. Das klappt an sich auch schon recht gut! ­čÖé

    Jetzt gehts ans eingemacht! ­čÖé

    hashmap.hh

    #ifndef hashmap_hh
      #define hashmap_hh
    
      #include <map>
      #include <iostream>
      #include <cstring>
      #include "stringutils.hh"
    
      namespace{
    
        using namespace std;
    
        class MapElement{
    
    	    private:
    		    string *filename;
    		    string *path;
    
    	    public:
    		    MapElement(string *f, string *p):filename(f), path(p){}
    			~MapElement(){
    			  cerr<<"Desktruktor: MapElement ["<<*filename<<","<<*path<<"] wird aufgerufen"<<endl;
    			  delete filename;
    			  delete path;
    			}
    		    string getFileName(){ return *filename; }
    		    string getPath(){ return *path; }
    
        };
    
        class HashMap{
    
    	    private:
    		    map<unsigned long, MapElement*> *hm;
    
    		    unsigned long& hash(string *key);
    
    	    public:
    			HashMap(){
    			  hm = new map<unsigned long, MapElement*>(); //auf dem Heap allozieren, da sehr gross werden kann
    			}
    			~HashMap(){
    			  cerr<<"Destruktor von HashMap wird aufgerufen"<<endl;
    			  map<unsigned long, MapElement*>::iterator it;
    			  for(it = hm->begin(); it != hm->end(); ++it){
    				delete ((*it).second);
    			  }
    			  delete hm;
    			}
    		    unsigned long put(string *k, MapElement *v);
    
        };
    
        unsigned long& HashMap::hash(string *key){
          char * buffer = new char[(*key).length()+1];
          strncpy(buffer, (*key).c_str(), (*key).length());
          static unsigned long result;      
          result = stringutils::hashSDBM(buffer);
          delete [] buffer;
          return (result);
        }
    
        unsigned long HashMap::put(string *k, MapElement *v){
    		unsigned long key = hash(k);
    
    		map<unsigned long, MapElement*>::iterator it = hm->find(key);  
    
    		if(it==hm->end()){
    		hm->insert(std::pair<unsigned long, MapElement*>(key, v));
    
    		cerr<<"INSERTED "<<key<<endl;
    		return 0;
    		}else{
    		cerr<<"Gabs schon: "<<v->getFileName()<<endl;      
    		return key;
    		}      
        }
      }
    #endif
    

    soweit so gut.

    Das ganze teste ich in der test.cc:

    #include "map.hh"
    #include "stringutils.hh"
    
    #include <iostream>
    
      HashMap *hm = new HashMap();
    
      int main(void){
    
        MapElement *m1; 
    
        string *a = new string("hello");
        string *b = new string("world");
        m1 = new MapElement(a,b);
        hm->put(a, m1);
    
        string *c = new string("thats");
        string *d = new string("a test");
        m1 = new MapElement(c,d);
        hm->put(c, m1);
    
        string *e = new string("hello");
        string *f = new string("test");
        m1 = new MapElement(e,f);
        hm->put(e, m1);
    
        delete hm;
    
        return 0;
      }
    

    alles kompiliert einwandfrei und fuehrt auch alles super aus (<hello, world>; <thats, a test>) wird hinzugef├╝gt, bei <hello, test> beschwert er sich, da es den key "hello" schon gibt!

    Also alles in allem sieht es relativ gut aus! Wenn ich JETZT aber das binary mit valgrind unter die Lupe nehme wird mir ein Memory Leak angezeigt!

    Der komplette Auszug von valgrind folgt:

    valgrind --leak-check=full --track-origins=yes ./shell 2>&1 > valgrind.txt
    ==8060== Memcheck, a memory error detector
    ==8060== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
    ==8060== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
    ==8060== Command: ./shell
    ==8060==
    ==8060== Conditional jump or move depends on uninitialised value(s)
    ==8060== at 0x4C2BFB8: strlen (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==8060== by 0x401376: stringutils::hashSDBM(char*) (in dev/map)
    ==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
    ==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
    ==8060== by 0x401F87: main (in dev/map)
    ==8060== Uninitialised value was created by a heap allocation
    ==8060== at 0x4C2AC27: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==8060== by 0x401CCC: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
    ==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
    ==8060== by 0x401F87: main (in dev/map)
    ==8060==
    ==8060== Conditional jump or move depends on uninitialised value(s)
    ==8060== at 0x4C2BFB8: strlen (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==8060== by 0x401392: stringutils::hashSDBM(char*) (in dev/map)
    ==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
    ==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
    ==8060== by 0x401F87: main (in dev/map)
    ==8060== Uninitialised value was created by a heap allocation
    ==8060== at 0x4C2AC27: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==8060== by 0x401CCC: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
    ==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
    ==8060== by 0x401F87: main (in dev/map)
    ==8060==
    ==8060== Conditional jump or move depends on uninitialised value(s)
    ==8060== at 0x40140B: stringutils::hashSDBM(char*) (in dev/map)
    ==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
    ==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
    ==8060== by 0x401F87: main (in dev/map)
    ==8060== Uninitialised value was created by a heap allocation
    ==8060== at 0x4C2AC27: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==8060== by 0x401382: stringutils::hashSDBM(char*) (in dev/map)
    ==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
    ==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
    ==8060== by 0x401F87: main (in dev/map)
    ==8060==
    INSERTED 7416051667693574450
    ==8060== Conditional jump or move depends on uninitialised value(s)
    ==8060== at 0x40140B: stringutils::hashSDBM(char*) (in dev/map)
    ==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
    ==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
    ==8060== by 0x40203F: main (in dev/map)
    ==8060== Uninitialised value was created by a heap allocation
    ==8060== at 0x4C2AC27: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==8060== by 0x401382: stringutils::hashSDBM(char*) (in dev/map)
    ==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
    ==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
    ==8060== by 0x40203F: main (in dev/map)
    ==8060==
    INSERTED 8269306963433084652
    ==8060== Conditional jump or move depends on uninitialised value(s)
    ==8060== at 0x40140B: stringutils::hashSDBM(char*) (in dev/map)
    ==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
    ==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
    ==8060== by 0x4020F7: main (in dev/map)
    ==8060== Uninitialised value was created by a heap allocation
    ==8060== at 0x4C2AC27: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==8060== by 0x401382: stringutils::hashSDBM(char*) (in dev/map)
    ==8060== by 0x401D0C: (anonymous namespace)::HashMap::hash(std::string*) (in dev/map)
    ==8060== by 0x401D63: (anonymous namespace)::HashMap::put(std::string*, (anonymous namespace)::MapElement*) (in dev/map)
    ==8060== by 0x4020F7: main (in dev/map)
    ==8060==
    Gabs schon: hello
    Destruktor von HashMap wird aufgerufen
    Desktruktor: MapElement [hello,world] wird aufgerufen
    Desktruktor: MapElement [thats,a test] wird aufgerufen
    ==8060==
    ==8060== HEAP SUMMARY:
    ==8060== in use at exit: 91 bytes in 5 blocks
    ==8060== total heap usage: 25 allocs, 20 frees, 464 bytes allocated
    ==8060==
    ==8060== 91 (16 direct, 75 indirect) bytes in 1 blocks are definitely lost in loss record 5 of 5
    ==8060== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==8060== by 0x4020C3: main (in dev/map)
    ==8060==
    ==8060== LEAK SUMMARY:
    ==8060== definitely lost: 16 bytes in 1 blocks
    ==8060== indirectly lost: 75 bytes in 4 blocks
    ==8060== possibly lost: 0 bytes in 0 blocks
    ==8060== still reachable: 0 bytes in 0 blocks
    ==8060== suppressed: 0 bytes in 0 blocks
    ==8060==
    ==8060== For counts of detected and suppressed errors, rerun with: -v
    ==8060== ERROR SUMMARY: 10 errors from 6 contexts (suppressed: 2 from 2)

    Also wenn ich die Meldung von valgrind richtig interpretiere, werden die longs f├╝r die Map (OHNE MEIN ZUTUN -_-) auf dem Heap allokiert und selbstredend sp├Ąter nicht mehr freigegeben!

    Hat irgendjemand eine Idee, wo mein Fehler ist, beziehungswei├če was ich besser machen kann?! Ich verzweifle hier n├Ąmlich bald und hab das ungute Gef├╝hl das ich einfach den Wald vor lauter B├Ąumen nicht sehe!!!

    Ich bedanke mich bereits im Vorraus f├╝r eure Hilfe und eure Zeit!

    MfG

    Hymir



  • Du hast die Regel der drei verletzt.

    vielleicht sind da noch mehr Fehler, aber immer einen Schritt nach dem anderen.



  • Du hast die Regel der drei verletzt.

    ? was hei├čt das denn? =O





  • ich sollte also noch ne copy operator und nen operator= schreiben und das sollte das problem l├Âsen?
    =O



  • Beim schnellen dr├╝ber schauen ist mir aufgefallen, dass Du die map mit new anlegst, mit dem Kommentar, dass sie sehr gro├č werden kann und Du sie daher auf dem Heap anlegen m├Âchtest. Die map selbst verwaltet aber bereits seine Daten auf dem Heap. Selbst wenn sie gro├č wird, wird nicht mehr Stack verbraucht. Sonst m├╝sste er ja dynamisch Stack verbrauchen, was ja eben nicht geht.

    Au├čerdem wozu kopierst Du in der Hash-Funktion Deine Daten? Du kannst direkt ├╝ber strToHash iterieren. Und warum wird der String als char* und nicht als const char* ├╝bergeben? Oder besser noch als const std::string&. Der R├╝ckgabewert ist auch sehr merkw├╝rdig. Du kannst direkt den Hash-Wert als unsigned long liefern, statt eine konstante Referenz. Dann brauchst Du auch keine statische Instanz von Deinem unsigned long, die sowieso fehlerhaft ist, da der Wert bei jedem Aufruf ├╝berschrieben wird.

    Bei Zeiger auf std::string wird mir ├╝bel. Entweder klassisch mit const char* oder gleich einfach std::string, aber Zeiger auf std::string ist eigentlich immer falsch.

    string *a = new string("hello");
    

    ist einfach nur falsch. Einfacher, sicherere und schneller ist das:

    string a = "hello"
    

    Da ist kein Speicherleck und der Code ist weitaus lesbarer.

    Dass Du bei diesen Zeigerwust Speicherlecks hast, wundert mich so rein gar nicht.

    Wenn ich noch weiter schauen w├╝rde, w├╝rde ich sicher noch viel mehr finden. Aber wie daddy_felix auch sagt: ein Schritt nach dem anderen.



  • Hymir90 schrieb:

    ich sollte also noch ne copy operator und nen operator= schreiben und das sollte das problem l├Âsen?
    =O

    es l├Âst auf jeden Fall einige Probleme. Ob es alle sind, wirst du dann ja sehen ­čśë



  • Hymir90 schrieb:

    ich sollte also noch ne copy operator und nen operator= schreiben und das sollte das problem l├Âsen?
    =O

    Ne, das glaube ich nicht. Aber hier stellen sich so viele Fragen, z.B. wieso dynamische Speicherverwaltung mit new, wieso rohe Zeiger, wieso reinterpreter-Casts, wieso dynamische Arrays mit new[], wieso ist der Value der map ein roher Zeiger, wieso kommt da nirgendwo const vor ­čśĽ Fragen ├╝ber Frange. All das zusammen f├╝hrt zu deinen Bugs.



  • stringutils.hh

    1. warum .hh als Endung? Ist eher ungew├Âhnlich. .h oder .hpp, seltener .hxx
    2. warum benutzt du <string.h>? (Der C++-Header hie├če <cstring>, wenn du die C-String Funktionen brauchst)
    3. using namespace std auf namespace-Ebene in einem header - vielleicht keine gute Idee
    4. wozu das tempor├Ąre char-array str in der Funktion? den hash kannst du genauso auf dem ├╝bergebene array berechnen.
    5. warum char* als Parameter und nicht char const*, wenn du das ├╝bergebene char-Array nicht ├Ąnderst?
    6. warum eine statische Variable hash und als R├╝ckgabe eine Referenz darauf???? ­čśĽ Das schreit nach verr├╝cktem, unerwarteten Verhalten
    7. wozu <iostream>, <sstream> und <string> einbinden, wenn du sie nicht nutzt?
    8. warum ist die Funktion nicht inline definiert? Damit hast du eine ODR-Verletzung, sobald du den header in mehr als einer ├ťbersetzungseinheit einbindest.

    hashmap.hh
    9) Warum wirfst du ├╝berall mit Pointern um dich? Das sieht schonmal arg nach Java-Abk├Âmmling aus, und da wundert es nicht mehr, warum du ├╝berall memleaks hast. Zumal du dann bei den Gettern von MapElement pl├Âtzlich Kopien zur├╝ck gibst, was wiederum absolut unn├Âtig ist.
    10) MapElement ├╝bernimmt offenbar den Besitz von filename und path (l├Âscht sie zumindest im DTor). Da du aber keinen op= und keinen Copy-Ctor erstellt hast, l├Ąufst du wenn du das Ding an eine std::map ├╝bergibst schneller auf double deletes als du "huch" sagen kannst.

    Da gibts noch viele weitere Punkte, aber nach der Pointerschlacht hab ich aufgegeben, weiter zu schauen. Mein Fazit: Dass du memleaks hast, ist nicht verwunderlich. Verwunderlich ist eher, dass Programm soweit durchl├Ąuft, dass valgrind dir irgendwas sagen kann, bevor dir das ganze Ding um die Ohren fliegt. Ich empfehle dringend, dich vom Referenz-Denken aus Java (oder C# oder woher auch immer du das hast) zu l├Âsen und mit einem guten C++-Buch die Grundlagen zu erarbeiten.



  • jawohl jawohl, ich gebs ja zu! ^^ Ich komm aus der Java-Ecke und hab grad echte Probleme mit den Pointern usw. Danke erstmal f├╝r die vielen Antworten. Ich werde mir das mal in Ruhe anschauen!

    MfG


  • Mod

    Man sollte mal erw├Ąhnen, dass die ganze Pr├Ąmisse bez├╝glich einer fehlenden Hashmap falsch ist:
    http://en.wikipedia.org/wiki/Unordered_associative_containers_(C%2B%2B)#History



  • Mal abgesehen hat C++ bereits eine Hashmap. std::unordered_map.

    Edit: Ach Mist, zu langsam ­čś×



  • Hymir90 schrieb:

    jawohl jawohl, ich gebs ja zu! ^^ Ich komm aus der Java-Ecke und hab grad echte Probleme mit den Pointern usw. Danke erstmal f├╝r die vielen Antworten. Ich werde mir das mal in Ruhe anschauen!

    Das macht aber gar nichts. Zeiger brauchst du in C++ nur selten. Deswegen kannst du Zeiger erstmal aus deinem Kopf streichen. ­čśë



  • In Boost und der C++11-Bibliothek gibts ├╝brigens eine unordered_map, d├╝rfte in deine Richtung gehen ­čśë

    Wie deine Hashfunktion aussehen k├Ânnte:

    #ifndef stringutils_hpp
    #define stringutils_hpp
    
    namespace stringutils{
      /**
         hashSDBM
         wandelt char* in Hashwert (SDBM - Algorithmus)
         @param strToHash            zu hashender String
         @return Hashwert
      */
      unsigned long hashSDBM(char const* strToHash){
        unsigned long hash = 0;
        for(;*strToHash;++strToHash)
          hash = *strToHash + (hash <<6) + (hash <<16) - hash;
        return hash;
        }
    
    #endif
    

    Wobei ich nicht sicher bin, ob das so klug ist, char* als Parameter zu haben, wenn hash ein unsigned long ist. char ist nicht notwendigerweise unsigned, so dass folgendes z.B. Murks erzeugt:
    hashSDBM("\x80") -> \x80 = (char)128 = -128 f├╝r signed char
    -> hash = -128 + (0<<6) + (0<<16) - 0 = -128 -> Unterlauf
    Ein Compiler sollte da auch eine Warnung bzgl. signed/unsigned mismatch liefern



  • pumuckl schrieb:

    Wobei ich nicht sicher bin, ob das so klug ist, char* als Parameter zu haben, wenn hash ein unsigned long ist. char ist nicht notwendigerweise unsigned, so dass folgendes z.B. Murks erzeugt:
    hashSDBM("\x80") -> \x80 = (char)128 = -128 f├╝r signed char
    -> hash = -128 + (0<<6) + (0<<16) - 0 = -128 -> Unterlauf
    Ein Compiler sollte da auch eine Warnung bzgl. signed/unsigned mismatch liefern

    An welcher Stelle genau soll es da eine Warnung geben und warum?
    W├╝rde static_cast<unsigned char>(*strToHash) deine hypothetische Warnung verstummen lassen?

    @Hymir90: Informiere dich, was tats├Ąchlich eine Hash Map ist und tut. Dein Ansatz verwendet den Hash als eindeutigen Schl├╝ssel f├╝r die std::map , obwohl nat├╝rlich mehrere Elemente den gleichen Hash haben k├Ânnen. Au├čerdem hat eine Hash Map typischerweise konstante Such- und Einf├╝gezeit, nicht logarithmische wie std::map .



  • out schrieb:

    Hymir90 schrieb:

    jawohl jawohl, ich gebs ja zu! ^^ Ich komm aus der Java-Ecke und hab grad echte Probleme mit den Pointern usw. Danke erstmal f├╝r die vielen Antworten. Ich werde mir das mal in Ruhe anschauen!

    Das macht aber gar nichts. Zeiger brauchst du in C++ nur selten. Deswegen kannst du Zeiger erstmal aus deinem Kopf streichen. ­čśë

    Ach ja? Wie macht ihr dass wenn ihr Referenzen auf Objekte oder sogar Listen mit Referenzen auf Objekte braucht?


  • Mod

    Butterbrot schrieb:

    Das macht aber gar nichts. Zeiger brauchst du in C++ nur selten. Deswegen kannst du Zeiger erstmal aus deinem Kopf streichen. ­čśë

    Ach ja? Wie macht ihr dass wenn ihr Referenzen auf Objekte oder sogar Listen mit Referenzen auf Objekte braucht?

    Mit Pointern. Aber das brauche ich nur selten. ­čÖé



  • Butterbrot schrieb:

    Ach ja? Wie macht ihr dass wenn ihr Referenzen auf Objekte oder sogar Listen mit Referenzen auf Objekte braucht?

    Referenzen auf Objekte -> Referenzen. Letzteres kommt so gut wie nie vor ud wird meistens durch Iteratoren ersetzt.

    //und und bei den wenigen F├Ąllen die ├╝brig bleiben Pointer. Aber dann h├Ąngt da meistens keine Speicherverwaltung mit dran.



  • Ich Frage nur weil ich mich gerade mit Design Patterns besch├Ąftige und dort st├Ąndig Pointer einsetze, dann mache ich wohl was falsch. Kann man denn eine Liste mit Referenzen haben, wie mache ich das mit Null Referenzen? Vielleicht NULL-Objekte erstellen?



  • Ja, Java in C++ ist eine ganz schlechte Idee.


Log in to reply