COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 10 years ago

#333 closed defect (fixed)

Valgrind reports memory error in min_mean_cycle_test

Reported by: Alpar Juttner Owned by: Balazs Dezso
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id: a2d5fd4c309a

Description

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)

Attachments (1)

921d5bf41ac2.patch (625 bytes) - added by Balazs Dezso 10 years ago.

Download all attachments as: .zip

Change History (6)

comment:1 in reply to:  description Changed 10 years ago by 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.

Changed 10 years ago by Balazs Dezso

Attachment: 921d5bf41ac2.patch added

comment:2 Changed 10 years ago by 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.

comment:3 in reply to:  2 ; Changed 10 years ago by 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.

comment:4 in reply to:  3 Changed 10 years ago by Peter Kovacs

Owner: changed from Alpar Juttner to Balazs Dezso

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

comment:5 Changed 10 years ago by Peter Kovacs

Resolution: fixed
Status: newclosed

[921d5bf41ac2] went to the main branch.

Note: See TracTickets for help on using tickets.