Valgrind reports memory error in min_mean_cycle_test

[Alpar Juttner]

valgrind ./min_mean_cycle_test
==4221== Memcheck, a memory error detector
==4221== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==4221== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==4221== Command: ./min_mean_cycle_test
==4221== 
==4221== Invalid read of size 4
==4221==    at 0x804B56B: lemon::SmartDigraphBase::source(lemon::SmartDigraphBase::Arc) const (smart_graph.h:100)
==4221==    by 0x80642E0: lemon::HartmannOrlin<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::HartmannOrlinDefaultTraits<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, true> >::checkTermination(int) (hartmann_orlin.h:601)
==4221==    by 0x805AED9: lemon::HartmannOrlin<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::HartmannOrlinDefaultTraits<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, true> >::processRounds() (hartmann_orlin.h:520)
==4221==    by 0x805456E: lemon::HartmannOrlin<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::HartmannOrlinDefaultTraits<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, true> >::findMinMean() (hartmann_orlin.h:342)
==4221==    by 0x804DD19: void checkMmcAlg<lemon::HartmannOrlin<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::HartmannOrlinDefaultTraits<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, true> > >(lemon::SmartDigraph const&, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int> const&, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int> const&, int, int) (min_mean_cycle_test.cc:113)
==4221==    by 0x804A26A: main (min_mean_cycle_test.cc:203)
==4221==  Address 0x430a704 is 12 bytes before a block of size 256 alloc'd
==4221==    at 0x4027400: operator new(unsigned int) (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==4221==    by 0x805C523: __gnu_cxx::new_allocator<lemon::SmartDigraphBase::ArcT>::allocate(unsigned int, void const*) (new_allocator.h:89)
==4221==    by 0x8055731: std::_Vector_base<lemon::SmartDigraphBase::ArcT, std::allocator<lemon::SmartDigraphBase::ArcT> >::_M_allocate(unsigned int) (stl_vector.h:140)
==4221==    by 0x804E93A: std::vector<lemon::SmartDigraphBase::ArcT, std::allocator<lemon::SmartDigraphBase::ArcT> >::_M_insert_aux(__gnu_cxx::__normal_iterator<lemon::SmartDigraphBase::ArcT*, std::vector<lemon::SmartDigraphBase::ArcT, std::allocator<lemon::SmartDigraphBase::ArcT> > >, lemon::SmartDigraphBase::ArcT const&) (vector.tcc:322)
==4221==    by 0x804C97E: std::vector<lemon::SmartDigraphBase::ArcT, std::allocator<lemon::SmartDigraphBase::ArcT> >::push_back(lemon::SmartDigraphBase::ArcT const&) (stl_vector.h:741)
==4221==    by 0x804B467: lemon::SmartDigraphBase::addArc(lemon::SmartDigraphBase::Node, lemon::SmartDigraphBase::Node) (smart_graph.h:85)
==4221==    by 0x804CBAA: lemon::DigraphExtender<lemon::SmartDigraphBase>::addArc(lemon::SmartDigraphBase::Node const&, lemon::SmartDigraphBase::Node const&) (graph_extender.h:274)
==4221==    by 0x804B848: lemon::SmartDigraph::addArc(lemon::SmartDigraphBase::Node, lemon::SmartDigraphBase::Node) (smart_graph.h:231)
==4221==    by 0x8052896: lemon::DigraphReader<lemon::SmartDigraph>::readArcs() (lgf_reader.h:1042)
==4221==    by 0x804D719: lemon::DigraphReader<lemon::SmartDigraph>::run() (lgf_reader.h:1154)
==4221==    by 0x8049EE1: main (min_mean_cycle_test.cc:194)
==4221== 
==4221== Invalid read of size 4
==4221==    at 0x804B56B: lemon::SmartDigraphBase::source(lemon::SmartDigraphBase::Arc) const (smart_graph.h:100)
==4221==    by 0x80642E0: lemon::HartmannOrlin<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::HartmannOrlinDefaultTraits<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, true> >::checkTermination(int) (hartmann_orlin.h:601)
==4221==    by 0x805AF68: lemon::HartmannOrlin<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::HartmannOrlinDefaultTraits<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, true> >::processRounds() (hartmann_orlin.h:527)
==4221==    by 0x805456E: lemon::HartmannOrlin<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::HartmannOrlinDefaultTraits<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, true> >::findMinMean() (hartmann_orlin.h:342)
==4221==    by 0x804DD19: void checkMmcAlg<lemon::HartmannOrlin<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::HartmannOrlinDefaultTraits<lemon::SmartDigraph, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, true> > >(lemon::SmartDigraph const&, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int> const&, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int> const&, int, int) (min_mean_cycle_test.cc:113)
==4221==    by 0x804A26A: main (min_mean_cycle_test.cc:203)
==4221==  Address 0x430a704 is 12 bytes before a block of size 256 alloc'd
==4221==    at 0x4027400: operator new(unsigned int) (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==4221==    by 0x805C523: __gnu_cxx::new_allocator<lemon::SmartDigraphBase::ArcT>::allocate(unsigned int, void const*) (new_allocator.h:89)
==4221==    by 0x8055731: std::_Vector_base<lemon::SmartDigraphBase::ArcT, std::allocator<lemon::SmartDigraphBase::ArcT> >::_M_allocate(unsigned int) (stl_vector.h:140)
==4221==    by 0x804E93A: std::vector<lemon::SmartDigraphBase::ArcT, std::allocator<lemon::SmartDigraphBase::ArcT> >::_M_insert_aux(__gnu_cxx::__normal_iterator<lemon::SmartDigraphBase::ArcT*, std::vector<lemon::SmartDigraphBase::ArcT, std::allocator<lemon::SmartDigraphBase::ArcT> > >, lemon::SmartDigraphBase::ArcT const&) (vector.tcc:322)
==4221==    by 0x804C97E: std::vector<lemon::SmartDigraphBase::ArcT, std::allocator<lemon::SmartDigraphBase::ArcT> >::push_back(lemon::SmartDigraphBase::ArcT const&) (stl_vector.h:741)
==4221==    by 0x804B467: lemon::SmartDigraphBase::addArc(lemon::SmartDigraphBase::Node, lemon::SmartDigraphBase::Node) (smart_graph.h:85)
==4221==    by 0x804CBAA: lemon::DigraphExtender<lemon::SmartDigraphBase>::addArc(lemon::SmartDigraphBase::Node const&, lemon::SmartDigraphBase::Node const&) (graph_extender.h:274)
==4221==    by 0x804B848: lemon::SmartDigraph::addArc(lemon::SmartDigraphBase::Node, lemon::SmartDigraphBase::Node) (smart_graph.h:231)
==4221==    by 0x8052896: lemon::DigraphReader<lemon::SmartDigraph>::readArcs() (lgf_reader.h:1042)
==4221==    by 0x804D719: lemon::DigraphReader<lemon::SmartDigraph>::run() (lgf_reader.h:1154)
==4221==    by 0x8049EE1: main (min_mean_cycle_test.cc:194)
==4221== 
==4221== 
==4221== HEAP SUMMARY:
==4221==     in use at exit: 0 bytes in 0 blocks
==4221==   total heap usage: 1,277 allocs, 1,277 frees, 111,504 bytes allocated
==4221== 
==4221== All heap blocks were freed -- no leaks are possible
==4221== 
==4221== For counts of detected and suppressed errors, rerun with: -v
==4221== ERROR SUMMARY: 24 errors from 2 contexts (suppressed: 5 from 5)

[Alpar Juttner]

Replying to alpar:

> ==4221==  Address 0x430a704 is 12 bytes before a block of size 256 alloc'd
> ==4221==    at 0x4027400: operator new(unsigned int) (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)

It looks like as if we wanted to read a -1 (INVALID?) index.

[Balazs Dezso]

I have uploaded a fix for the issue in patch [921d5bf41ac2]. The first node on the path does not have predecessor arc, therefore the source cannot be obtained.

It might be better solution, if we set a fake arc instead of INVALID and the if statement doesn't have to be used. Alternatively, the loop can be reorganized.

[Alpar Juttner]

Replying to deba:

I have uploaded a fix for the issue in patch [921d5bf41ac2]. The first node on the path does not have predecessor arc, therefore the source cannot be obtained.

It might be better solution, if we set a fake arc instead of INVALID and the if statement doesn't have to be used. Alternatively, the loop can be reorganized.

Peter, please let me know if you are happy with this solution.

[Peter Kovacs]

Replying to alpar:

Peter, please let me know if you are happy with this solution.

It's perfect. (I don't think this 'if' is critical efficiency question.)

[Peter Kovacs]

[921d5bf41ac2] went to the main branch.