Re: [Boost-users] BGL: *** glibc detected *** free(): invalid next size - UPDATE

From: Irek Szczesniak (ijs_at_[hidden])
Date: 2006-04-23 14:50:02

I'm writing with an update on my problem.  I'm using Fedora Core 3,
Linux 2.6.10, GCC 3.4.4.

The description of my error is given in the documentation of glibc:

 > The version of glibc provided with Red Hat Enterprise Linux 4
 > performs additional internal sanity checks to prevent and detect
 > data corruption as early as possible. By default, should corruption
 > be detected, a message similar to the following will be displayed on
 > standard error (or logged via syslog if stderr is not open):
 >
 > *** glibc detected *** double free or corruption: 0x0937d008 ***

So it seems there are problems with memory allocation.  To see what's
up, I ran valgrind on my code and I got many errors of this kind:

==6464== Invalid write of size 4
==6464==    at 0x805E917: void put<int, int>(int*, int, int const&) 
(property_map.hpp:134)
==6464==    by 0x805C503: void 
boost::dijkstra_shortest_paths<boost::adjacency_list<boost::vecS, 
boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, 
std::string, boost::property<boost::vertex_distance_t, 
std::vector<int, std::allocator<int> >, 
boost::property<boost::vertex_predecessor_t, std::vector<unsigned, 
std::allocator<unsigned> >, boost::no_property> > >, 
boost::property<boost::edge_weight_t, int, 
boost::property<boost::edge_weight2_t, int, boost::no_property> >, 
boost::no_property, boost::listS>, 
boost::dijkstra_visitor<boost::null_visitor>, unsigned*, int*, 
boost::adj_list_edge_property_map<boost::undirected_tag, int, int 
const&, unsigned, boost::property<boost::edge_weight2_t, int, 
boost::no_property> const, boost::edge_weight_t>, 
boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_name_t, 
std::string, boost::property<boost::vertex_distance_t, 
std::vector<int, std::allocator<int> >, 
boost::property<boost::vertex_predecessor_t, std::vector<unsigned, 
std::allocator<unsigned> >, boost::no_property> > >, unsigned>, 
std::less<int>, boost::closed_plus<int>, int, int, 
boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, 
std::vector<boost::closed_plus, std::allocator<boost::closed_plus> > 
 >, boost::property<boost::edge_weight2_t, int, boost::no_property> 
const, boost::closed_plus, boost::closed_plus&> 
 >(boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, 
boost::property<boost::vertex_name_t, std::string, 
boost::property<boost::vertex_distance_t, std::vector<int, 
std::allocator<int> >, boost::property<boost::vertex_predecessor_t, 
std::vector<unsigned, std::allocator<unsigned> >, boost::no_property> 
 > >, boost::property<boost::edge_weight_t, int, 
boost::property<boost::edge_weight2_t, int, boost::no_property> >, 
boost::no_property, boost::listS> const&, 
boost::graph_traits<std::allocator<boost::closed_plus> 
 >::vertex_descriptor, unsigned*, int*, 
boost::adj_list_edge_property_map<boost::undirected_tag, int, int 
const&, unsigned, boost::property<boost::edge_weight2_t, int, 
boost::no_property> const, boost::edge_weight_t>, 
boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_name_t, 
std::string, boost::property<boost::vertex_distance_t, 
std::vector<int, std::allocator<int> >, 
boost::property<boost::vertex_predecessor_t, std::vector<unsigned, 
std::allocator<unsigned> >, boost::no_property> > >, unsigned>, 
std::less<int>, boost::closed_plus<int>, int, int, 
boost::dijkstra_visitor<boost::null_visitor>, 
boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, 
std::vector<boost::closed_plus, std::allocator<boost::closed_plus> > 
 >, boost::property<boost::edge_weight2_t, int, boost::no_property> 
const, boost::closed_plus, boost::closed_plus&>) 
(dijkstra_shortest_paths.hpp:250)

Unfortunately, my knowledge of BGL and its implementation techniques
is modest and so I will not venture to find out what the problem
exactly is.  Instead, I rewrote the broken piece of code this way:

   vector<int> dist(num_vertices(g));
   vector<Vertex> pred(num_vertices(g));

   BGL_FORALL_VERTICES (v, g, Graph)
     {
       dijkstra_shortest_paths
        (g, v, predecessor_map(&pred[0]).distance_map(&dist[0]));

       put(vertex_distance, g, v, dist);
       put(vertex_predecessor, g, v, pred);
     }

This works for me, and neither glibc nor valgrind complain.  The
complete text of my program is at the bottom of this email.

I don't think there is any performance blow from using vectors as
properties.  Whenever I need to access these properties I write:
get(vertex_distance, g, i) or get(vertex_distance, g, i)[j].  I get
references so the properties (which are vectors) are not copied.

Best,
Irek

Irek Szczesniak wrote:

 > Vertexes in my graph have the distance and predecessor
 > properties. These properties at each vertex are vectors: they store
 > distances and predecessor of shortest paths to every other node in
 > the graph.
 >
 > Below is my program.  I run the program and as input I give the file
 > also listed below, and get this run-time error:
 >
 > *** glibc detected *** free(): invalid next size (fast): 0x085dd110
 >
 > I would appreciate your advice on what I'm doing wrong.
 >
 >
 > Best,
 > Irek
 >
 > (...)

********************************************************************

#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/graphviz.hpp>

using namespace std;
using namespace boost;

typedef
adjacency_list_traits<vecS, vecS, undirectedS>::vertex_descriptor
Vertex;

typedef
boost::adjacency_list <vecS, vecS, undirectedS,
        property<vertex_name_t, string,
        property<vertex_distance_t, vector<int>,
        property<vertex_predecessor_t, vector<Vertex> > > >,
        property<edge_weight_t, int,
        property<edge_weight2_t, int> > >
Graph;

int
main ()
{
   Graph g;
   dynamic_properties dp;

   dp.property("node_id", get(vertex_name, g));
   dp.property("distance", get(edge_weight, g));
   dp.property("lambdas", get(edge_weight2, g));

   read_graphviz(cin, g, dp);

   // My implementation now is this:

   vector<int> dist(num_vertices(g));
   vector<Vertex> pred(num_vertices(g));

   BGL_FORALL_VERTICES (v, g, Graph)
     {
       dijkstra_shortest_paths
        (g, v, predecessor_map(&pred[0]).distance_map(&dist[0]));

       put(vertex_distance, g, v, dist);
       put(vertex_predecessor, g, v, pred);
     }

   // This is what I used before:
   //
   // BGL_FORALL_VERTICES(v, g, Graph)
   //   {
   //     get(vertex_distance, g, v).resize(num_vertices(g));
   //     get(vertex_predecessor, g, v).resize(num_vertices(g));
   //
   //     dijkstra_shortest_paths
   //       (g, v, predecessor_map(&get(vertex_predecessor, g, v)[0]).
   //              distance_map(&get(vertex_distance, g, v)[0]));
   //   }
}