[C++] Individuazione leak memory

[fracarro]

Salve ragazzi.
Da qualche giorno sto provando una libreria free disponibile su internet ( la lemon versione 0.7) che mette a disposizione numerosi algoritmi di ottimizzazione su grafi. Ho provato vari algoritmi e mi sembra comportarsi bene tranne che per l'arborescence. In pratica questo metodo lavora correttamente ma alloca della memoria senza deallocarla, Chiamando quindi migliaia di volte la funzione vengono saturati i miei 2 GB di memoria in meno di 5 minuti. Ho cercato di individuare qual'è l'oggetto che non viene deallocato utilizzando in valgrind il quale mi riporta queste informazioni (ripetuta più volte):

==1330== 516,352 (126,900 direct, 389,452 indirect) bytes in 6,345 blocks are definitely lost in loss record 36 of 40
==1330== at 0x4023294: operator new(unsigned) (vg_replace_malloc.c:224)
==1330== by 0x80608D4: lemon::MinCostArborescence<lemon::SmartGraph, lemon::GraphExtender<lemon::SmartGraphBase>::EdgeMap<double>, lemon::MinCostArborescenceDefaultTraits<lemon::SmartGraph, lemon::GraphExtender<lemon::SmartGraphBase>::EdgeMap<double> > >::initStructures() (min_cost_arborescence.h:635)
==1330== by 0x8060907: lemon::MinCostArborescence<lemon::SmartGraph, lemon::GraphExtender<lemon::SmartGraphBase>::EdgeMap<double>, lemon::MinCostArborescenceDefaultTraits<lemon::SmartGraph, lemon::GraphExtender<lemon::SmartGraphBase>::EdgeMap<double> > >::init() (min_cost_arborescence.h:495)
==1330== by 0x8060AD6: lemon::MinCostArborescence<lemon::SmartGraph, lemon::GraphExtender<lemon::SmartGraphBase>::EdgeMap<double>, lemon::MinCostArborescenceDefaultTraits<lemon::SmartGraph, lemon::GraphExtender<lemon::SmartGraphBase>::EdgeMap<double> > >::run(lemon::SmartGraphBase::Node) (min_cost_arborescence.h:604)

............................................................................

Purtroppo però non essendo un esperto di c++ non ho capito se il problema risiede nella classe arborescence oppure in qualche altra classe. Qualcuno può aiutarmi? Allego anche il file .h (non c'è il .c) di questa classe.

[sottovento]

Non conosco questa libreria, ma sembra che il problema sia nel tuo codice.
La init() deve essere chiamata una sola volta.
Puoi postare il tuo codice?

[fracarro]

Originariamente inviato da sottovento

Non conosco questa libreria, ma sembra che il problema sia nel tuo codice.
La init() deve essere chiamata una sola volta.
Puoi postare il tuo codice?

Allora di seguito riporto la funzione che ho scritto (è un ibrido tra c e c++) in cui utilizzo la mincostarborescence.

long Arborescence(node *radice){

	using namespace std;
	nodo_lista *coda;
	nodo_lista *nodo_lista_temp;
	node *ptr;
	long sel,temp_value;


	typedef SmartGraph Graph;
	GRAPH_TYPEDEFS(Graph);

	typedef Graph::EdgeMap<double> CostMap;
	//typedef Graph::EdgeMap<bool> Arb;

	Graph graph;
	CostMap cost(graph);
	vector<Node> nodes;

	//Arb arb_edge(graph);
  
  	ptr=grafo_residuo; 	//puntatore per scorrere il grafo residuo

	while(ptr != ptr->gr_down){
			//NODES++;		
			nodes.push_back(graph.addNode());
			//printf("%d->%d, ",ptr->ID,NODES-1);
			ptr = ptr->gr_down;
	}
	//NODES++;		
	nodes.push_back(graph.addNode());
	//printf("%d->%d\n",ptr->ID,NODES-1);

	ptr=grafo_residuo;
	while(ptr != ptr->gr_down){
		
			coda = ptr->corona_entrante;	
			if(coda != NULL){	
				while( coda != coda->down){
					//EDGES++;
					Edge edge = graph.addEdge(nodes[City[coda->i].indice_costo_ridotto], nodes[City[coda->j].indice_costo_ridotto]);
					if(coda->i==radice->ID)
						cost[edge] = FEW_LARGE + coda->costo - u[City[coda->i].indice_costo_ridotto] - v[City[coda->j].indice_costo_ridotto];
					else cost[edge] = coda->costo - u[City[coda->i].indice_costo_ridotto] - v[City[coda->j].indice_costo_ridotto];
					//cout << "(" << graph.id(graph.source(edge)) << "," << graph.id(graph.target(edge)) << ")="<< cost[edge] << ", ";
					coda = coda->down;
				}	
				//EDGES++;
				Edge edge = graph.addEdge(nodes[City[coda->i].indice_costo_ridotto], nodes[City[coda->j].indice_costo_ridotto]);
				if(coda->i==radice->ID)
						cost[edge] = FEW_LARGE + coda->costo - u[City[coda->i].indice_costo_ridotto] - v[City[coda->j].indice_costo_ridotto];
				else cost[edge] = coda->costo - u[City[coda->i].indice_costo_ridotto] - v[City[coda->j].indice_costo_ridotto];
				
				//cout << "(" << graph.id(graph.source(edge)) << "," << graph.id(graph.target(edge)) << ")="<< cost[edge] << endl;
			}
			ptr = ptr->gr_down;
	}

	coda = ptr->corona_entrante;	
	if(coda != NULL){	
		while( coda != coda->down){
			//EDGES++;
			Edge edge = graph.addEdge(nodes[City[coda->i].indice_costo_ridotto], nodes[City[coda->j].indice_costo_ridotto]);
			if(coda->i==radice->ID)
				cost[edge] = FEW_LARGE + coda->costo - u[City[coda->i].indice_costo_ridotto] - v[City[coda->j].indice_costo_ridotto];
			else cost[edge] = coda->costo - u[City[coda->i].indice_costo_ridotto] - v[City[coda->j].indice_costo_ridotto];
			//cout << "(" << graph.id(graph.source(edge)) << "," << graph.id(graph.target(edge)) << ")="<< cost[edge] << ", ";
			coda = coda->down;
		}	
		//EDGES++;
		Edge edge = graph.addEdge(nodes[City[coda->i].indice_costo_ridotto], nodes[City[coda->j].indice_costo_ridotto]);
		if(coda->i==radice->ID)
				cost[edge] = FEW_LARGE + coda->costo - u[City[coda->i].indice_costo_ridotto] - v[City[coda->j].indice_costo_ridotto];
		else cost[edge] = coda->costo - u[City[coda->i].indice_costo_ridotto] - v[City[coda->j].indice_costo_ridotto];
		
		//cout << "(" << graph.id(graph.source(edge)) << "," << graph.id(graph.target(edge)) << ")="<< cost[edge] << endl;
	}

	Node source = nodes[radice->indice_costo_ridotto];

	MinCostArborescence<Graph, CostMap> mca(graph, cost);
	mca.run(source);

	temp_value = mca.arborescenceValue();

	for(EdgeIt i(graph); i!=INVALID; ++i){

		if (graph.source(i)==source && mca.arborescence(i))
		  temp_value -= FEW_LARGE;
	}

	return temp_value;
}

La funzione deve semplicemente restituire un valore. La init() viene invocata internamente dal metodo run(source) (il quale in realtà fa tre operazioni: mca.init(); mca.addSource(s); mca.start() ) e credo sia giusto così perchè ha bisogno di allocare ed inizializzare le sue strutture per risolvere il problema.

P.S. Non badate al codice che è scritto con i piedi ma mi serve verificare le performance di questi algoritmi e quindi non ho badato alla leggibilità.

[sottovento]

In effetti c'e' qualcosa di strano, ma non nel tuo codice.
Non riesco a capire la parte che va a deallocare (presa da min_cost_arborescence.h):

    void destroyStructures() {
      if (local_arborescence) {
        delete _arborescence;
      }
      if (local_pred) {
        delete _pred;
      }
      if (!_edge_order) {
        delete _edge_order;
      }
      if (_node_order) {
        delete _node_order;
      }
      if (!_cost_edges) {
        delete _cost_edges;
      }
      if (!_heap) {
        delete _heap;
      }
      if (!_heap_cross_ref) {
        delete _heap_cross_ref;
      }
    }

Valgrind ti dice che la variabile membro _heap non viene deallocata.
In effetti sembra che si faccia la delete SOLO se _heap == NULL, che ovviamente non serve.

In sostanza, sembra che quel punto esclamativo (tutti i 3 punti esclamativi) non servano, anzi siano dannosi.

Siccome questo codice e' simile a quello della initStructures(), mi verrebbe in mente che il programmatore abbia fatto un copy&paste, e poi non abbia aggiornato tutti gli if ma solo i primi....

[fracarro]

Originariamente inviato da sottovento

In effetti c'e' qualcosa di strano, ma non nel tuo codice.
Non riesco a capire la parte che va a deallocare (presa da min_cost_arborescence.h):

    void destroyStructures() {
      if (local_arborescence) {
        delete _arborescence;
      }
      if (local_pred) {
        delete _pred;
      }
      if (!_edge_order) {
        delete _edge_order;
      }
      if (_node_order) {
        delete _node_order;
      }
      if (!_cost_edges) {
        delete _cost_edges;
      }
      if (!_heap) {
        delete _heap;
      }
      if (!_heap_cross_ref) {
        delete _heap_cross_ref;
      }
    }

Valgrind ti dice che la variabile membro _heap non viene deallocata.
In effetti sembra che si faccia la delete SOLO se _heap == NULL, che ovviamente non serve.

In sostanza, sembra che quel punto esclamativo (tutti i 3 punti esclamativi) non servano, anzi siano dannosi.

Siccome questo codice e' simile a quello della initStructures(), mi verrebbe in mente che il programmatore abbia fatto un copy&paste, e poi non abbia aggiornato tutti gli if ma solo i primi....

SSSSIIIIIIIIIIIIIIIIIII !!!!!!!!!!!
Ho modificato il file .h e adesso sembra funzionare correttamente.
Grazie mille.

[sottovento]

Originariamente inviato da fracarro

SSSSIIIIIIIIIIIIIIIIIII !!!!!!!!!!!
Ho modificato il file .h e adesso sembra funzionare correttamente.
Grazie mille.

Se quella e' una libreria open source, magari spedisci loro una email per avvertirli del "bug", cosi' che lo possano sistemare...

[fracarro]

Originariamente inviato da sottovento

Se quella e' una libreria open source, magari spedisci loro una email per avvertirli del "bug", cosi' che lo possano sistemare...

Lo stavo per fare ma ho visto che sul sito hanno già inserito una versione patchata dell'algoritmo che dovrebbe essere inserita nella versione 1.1 della libreria. Grazie ancora.