Valgrind and STL

[wwfarch]

I'm working on creating a K-Nearest Neighbor classifier and having some problems that I can't figure out. I have a header file KNNClassifier.h and its class file KNNClassifier.cc

In KNNClassifier.h I have the following declarations:

class KNNClassifier{
...
map<int, string> classNames;
map<int, DataStore*> lastDataStores;
map<int, int*> classificationMap;
map<int, int> indexMap;
vector<double> scaleVector;
...
};

Everything worked fine until I added classificationMap and indexMap. After adding those two variables the program seg faults near the end of the KNNClassifier constructor. If I comment out either one of them (it doesn't matter which) the program will complete but Valgrind reports the same type of read/write errors but there is no seg fault. The relevant Valgrind output is below the constructor code snippet.

KNNClassifier::KNNClassifier(int numNeighbors)
{
ENTERCONSTRUCTOR;
    statsInitialized = false;
    classificationMatrix = NULL;
    totalClassified = NULL;
    classifiedCorrectly = NULL;
    isTrained = false;
    K = numNeighbors;
    numVectors = 0;
    maxVectors = 10;
    trainedFeatures = (FeatureVector**)malloc(sizeof(FeatureVector*) * maxVectors);
LEAVECONSTRUCTOR;
}

The seg fault occurs at the last line when trainedFeatures is malloced in Valgrind but somewhere else when Valgrind is not running. Regardless I think the segfault is a symptom of the memory problems with STL.

==11646== 75 errors in context 53 of 57:
==11646== Invalid read of size 4
==11646== at 0x804F07D: std::vector<double, std::allocator<double> >::begin() const (stl_vector.h:342)
==11646== by 0x805268D: std::vector<double, std::allocator<double> >::vector(std::vector<double, std::allocator<double> > const&) (stl_vector.h:234)
==11646== by 0x805695B: KNNClassifier::classifyFeatures(std::vector<double , std::allocator<double> >) (KNNClassifier.cc:436)
==11646== by 0x8057B95: KNNClassifier::classifyFromFile(char*, char*, char*) (KNNClassifier.cc:281)
==11646== by 0x805CCD1: main (main.cc:71)
==11646== Address 0x567EB10 is 12 bytes after a block of size 100 alloc'd
==11646== at 0x4021DC5: operator new(unsigned) (vg_replace_malloc.c:163)
==11646== by 0x805CBE4: main (main.cc:55)
==11646==
==11646== 75 errors in context 54 of 57:
==11646== Invalid read of size 4
==11646== at 0x804F0A9: std::vector<double, std::allocator<double> >::end() const (stl_vector.h:360)
==11646== by 0x8052673: std::vector<double, std::allocator<double> >::vector(std::vector<double, std::allocator<double> > const&) (stl_vector.h:234)
==11646== by 0x805695B: KNNClassifier::classifyFeatures(std::vector<double , std::allocator<double> >) (KNNClassifier.cc:436)
==11646== by 0x8057B95: KNNClassifier::classifyFromFile(char*, char*, char*) (KNNClassifier.cc:281)
==11646== by 0x805CCD1: main (main.cc:71)
==11646== Address 0x567EB14 is not stack'd, malloc'd or (recently) free'd
==11646==
==11646== 75 errors in context 55 of 57:
==11646== Invalid read of size 4
==11646== at 0x804F0A9: std::vector<double, std::allocator<double> >::end() const (stl_vector.h:360)
==11646== by 0x804F134: std::vector<double, std::allocator<double> >::size() const (stl_vector.h:402)
==11646== by 0x805261F: std::vector<double, std::allocator<double> >::vector(std::vector<double, std::allocator<double> > const&) (stl_vector.h:233)
==11646== by 0x805695B: KNNClassifier::classifyFeatures(std::vector<double , std::allocator<double> >) (KNNClassifier.cc:436)
==11646== by 0x8057B95: KNNClassifier::classifyFromFile(char*, char*, char*) (KNNClassifier.cc:281)
==11646== by 0x805CCD1: main (main.cc:71)
==11646== Address 0x567EB14 is not stack'd, malloc'd or (recently) free'd
==11646==
==11646== 75 errors in context 56 of 57:
==11646== Invalid read of size 4
==11646== at 0x804F07D: std::vector<double, std::allocator<double> >::begin() const (stl_vector.h:342)
==11646== by 0x804F119: std::vector<double, std::allocator<double> >::size() const (stl_vector.h:402)
==11646== by 0x805261F: std::vector<double, std::allocator<double> >::vector(std::vector<double, std::allocator<double> > const&) (stl_vector.h:233)
==11646== by 0x805695B: KNNClassifier::classifyFeatures(std::vector<double , std::allocator<double> >) (KNNClassifier.cc:436)
==11646== by 0x8057B95: KNNClassifier::classifyFromFile(char*, char*, char*) (KNNClassifier.cc:281)
==11646== by 0x805CCD1: main (main.cc:71)
==11646== Address 0x567EB10 is 12 bytes after a block of size 100 alloc'd
==11646== at 0x4021DC5: operator new(unsigned) (vg_replace_malloc.c:163)
==11646== by 0x805CBE4: main (main.cc:55)
==11646==
==11646== 216 errors in context 57 of 57:
==11646== Invalid read of size 4
==11646== at 0x804F44A: __gnu_cxx::__normal_iterator<double*, std::vector<double, std::allocator<double> > >::__normal_iterator(double* const&) (stl_iterator.h:650)
==11646== by 0x804F4C4: std::vector<double, std::allocator<double> >::begin() (stl_vector.h:333)
==11646== by 0x805242D: std::vector<double, std::allocator<double> >::operator[](unsigned) (stl_vector.h:480)
==11646== by 0x80550B2: KNNClassifier::calcFeatureScale() (KNNClassifier.cc:706)
==11646== by 0x8058479: KNNClassifier::trainFromFile(char*, char*) (KNNClassifier.cc:185)
==11646== by 0x805CC93: main (main.cc:65)
==11646== Address 0x567EB10 is 12 bytes after a block of size 100 alloc'd
==11646== at 0x4021DC5: operator new(unsigned) (vg_replace_malloc.c:163)
==11646== by 0x805CBE4: main (main.cc:55)

[weaknessforcats]

This is not a good idea:

map<int, DataStore*> lastDataStores;
map<int, int*> classificationMap;
 

You have no idea of the pointers are valid when you use them. STL Containers tend to move things around and the container may delete your DataStore* which will delete the object and make the copy invalid.

I recommend that you use handles in your containers instead of pointers. If you are unsure what I am talkin about, see my article on Handle classes in the C++ Articles section of this web site.

Also, stop using malloc(). Constructors are not called so your allocation has not been initialized. malloc() and its ilk should never be used in STL and never in C++ either, for that matter.

[wwfarch]

I realize that malloc and pointers are unsafe. However, errors are being reported in the constructor before the vector/maps are even touched so that shouldn't really be the issue here should it?

[wwfarch]

Ok, so I've updated the code to eliminate the pointers and malloc. Now I have

class KNNClassifier
{
...
vector<FeatureVector> trainedFeatures;
...
map<int, string> classNames;
map<int, DataStore> lastDataStores;
map<int, vector<int> > classMap;
map<int, int> indexMap;
 
vector<double> scaleVector;
...
};

and the constructor now looks like this:

KNNClassifier::KNNClassifier(int numNeighbors)
{
ENTERCONSTRUCTOR;
    /*
     * Initialize all classifier parameters
     */
    statsInitialized = false;
    classificationMatrix = NULL;
    totalClassified = NULL;
    classifiedCorrectly = NULL;
    isTrained = false;
    K = numNeighbors;
    numVectors = 0;
    maxVectors = 10;
LEAVECONSTRUCTOR;
}

I'm still getting the same seg fault and errors reported by Valgrind. The errors appear to be happening during template instantiation. I've included a couple of the errors from Valgrind but there is one of these errors for each template in the header.

==6420== Invalid write of size 4
==6420== at 0x805A414: std::_Rb_tree<int, std::pair<int const, std::vector<int, std::allocator<int> > >, std::_Select1st<std::pair<int const, std::vector<int, std::allocator<int> > > >, std::less<int>, std::allocator<std::pair<int const, std::vector<int, std::allocator<int> > > > >::_Rb_tree_impl<std::less<int>, false>::_Rb_tree_impl(std::allocator<std::_Rb_tree _node<std::pair<int const, std::vector<int, std::allocator<int> > > > > const&, std::less<int> const&) (stl_tree.h:407)
==6420== by 0x805A47A: std::_Rb_tree<int, std::pair<int const, std::vector<int, std::allocator<int> > >, std::_Select1st<std::pair<int const, std::vector<int, std::allocator<int> > > >, std::less<int>, std::allocator<std::pair<int const, std::vector<int, std::allocator<int> > > > >::_Rb_tree(std::less<int> const&, std::allocator<std::pair<int const, std::vector<int, std::allocator<int> > > > const&) (stl_tree.h:562)
==6420== by 0x805A4B1: std::map<int, std::vector<int, std::allocator<int> >, std::less<int>, std::allocator<std::pair<int const, std::vector<int, std::allocator<int> > > > >::map() (stl_map.h:157)
==6420== by 0x805703E: KNNClassifier::KNNClassifier(int) (KNNClassifier.cc:31)
==6420== by 0x805DAF6: main (main.cc:55)
==6420== Address 0x567EB0C is 8 bytes after a block of size 100 alloc'd
==6420== at 0x4021DC5: operator new(unsigned) (vg_replace_malloc.c:163)
==6420== by 0x805DAE0: main (main.cc:55)
==6420==
==6420== Invalid write of size 4
==6420== at 0x805A438: std::_Rb_tree<int, std::pair<int const, std::vector<int, std::allocator<int> > >, std::_Select1st<std::pair<int const, std::vector<int, std::allocator<int> > > >, std::less<int>, std::allocator<std::pair<int const, std::vector<int, std::allocator<int> > > > >::_Rb_tree_impl<std::less<int>, false>::_Rb_tree_impl(std::allocator<std::_Rb_tree _node<std::pair<int const, std::vector<int, std::allocator<int> > > > > const&, std::less<int> const&) (stl_tree.h:411)
==6420== by 0x805A47A: std::_Rb_tree<int, std::pair<int const, std::vector<int, std::allocator<int> > >, std::_Select1st<std::pair<int const, std::vector<int, std::allocator<int> > > >, std::less<int>, std::allocator<std::pair<int const, std::vector<int, std::allocator<int> > > > >::_Rb_tree(std::less<int> const&, std::allocator<std::pair<int const, std::vector<int, std::allocator<int> > > > const&) (stl_tree.h:562)
==6420== by 0x805A4B1: std::map<int, std::vector<int, std::allocator<int> >, std::less<int>, std::allocator<std::pair<int const, std::vector<int, std::allocator<int> > > > >::map() (stl_map.h:157)
==6420== by 0x805703E: KNNClassifier::KNNClassifier(int) (KNNClassifier.cc:31)
==6420== by 0x805DAF6: main (main.cc:55)
==6420== Address 0x567EB04 is 0 bytes after a block of size 100 alloc'd
==6420== at 0x4021DC5: operator new(unsigned) (vg_replace_malloc.c:163)
==6420== by 0x805DAE0: main (main.cc:55)

[weaknessforcats]

This is not correct:

I realize that malloc and pointers are unsafe. However, errors are being reported in the constructor before the vector/maps are even touched so that shouldn't really be the issue here should it?

By the time you get to the { of your constructor, the maps have already been allocated and their default constructors called.

I compiled this code with no errors using Visual Studio.NET 2005

#include <iostream>
using namespace std;
#include <vector>
#include <map>
 
class DataStore
{
 
};
class FeatureVector
{
 
};
 
class KNNClassifier
{
//...
vector<FeatureVector> trainedFeatures;
//...
map<int, string> classNames;
map<int, DataStore> lastDataStores;
map<int, vector<int> > classMap;
map<int, int> indexMap;
 
vector<double> scaleVector;
//...
};
 
int main()
{
     KNNClassifier  k;
}
 

There's something else going on.

I will be more than happy to add your KNNClassifier constructor if you tell me what the data members are that you initialize in your constructor.

[wwfarch]

This is not correct:



By the time you get to the { of your constructor, the maps have already been allocated and their default constructors called.

I compiled this code with no errors using Visual Studio.NET 2005

My problem wasn't in compilation, it was a run time error. I actually managed to get the problem solved but it still doesn't make sense to me why it was manifesting during the constructor. There was a double free towards the end of my program long after the constructor had been called.

[weaknessforcats]

Consider using handles.

You can never delete in a C++ program unless you know you have the last pointer to that resource. That means the single most dangerous thing you can do in C++ is pass pointers around.

See my article on Handle Classes in the C/C++ Articles section.

[wkailey]

This is an STL bug, IMO.