4 Replies - 522 Views - Last Post: 18 September 2012 - 08:30 PM Rate Topic: -----

#1 Fa773N M0nK  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 18-September 12

Segmentation Fault, free() and scanf()

Posted 18 September 2012 - 10:52 AM

Hey, I have this huge source that is producing a Segmentation Fault.

I debugged it using CodeBlocks and it seems that it is segfaulting when it hits
scanf ( "%u", &no_lines );
for the second time. ( Line no. 31, in the code given below )

I also noticed that skipping the call to "dijkstra_deallocate()" stops the SegFault error.

What might be going wrong?



This is the file containing main()

#include <stdio.h>
#include "dijkstra.h"
#include <math.h>

#define MAX_NO_OF_LINES 100


unsigned int get_graph ( unsigned int, bool **, int ** );

unsigned int get_max_length ( unsigned int, int **, int *, unsigned int * , unsigned int );

int main ( void )
{
	unsigned int no_test_cases;
	scanf ( "%u", &no_test_cases );
	
	unsigned int no_lines;
	
	bool **edge_existance;
	int **adjacency_matrix;
	unsigned int *previous;
	int *tag;
	
	unsigned int no_nodes;
	unsigned int offset;
	unsigned int max_length;
	
	unsigned int i;
	for ( i = 0; i < no_test_cases; i++ )
	{
		scanf ( "%u", &no_lines );
	
		no_nodes = ( ( (no_lines) * (no_lines+1) ) / 2 ) + 1;
	
	
		dijkstra_allocate ( no_nodes, &edge_existance, &adjacency_matrix, &previous, &tag );
	
		offset = get_graph ( no_lines, edge_existance, adjacency_matrix );
	
		dijkstra ( no_nodes, edge_existance, adjacency_matrix, previous, tag );
	
		max_length = get_max_length ( no_lines, adjacency_matrix, tag, previous, offset );
	
		printf ( "%u\n", max_length);
	
		dijkstra_deallocate ( no_nodes, edge_existance, adjacency_matrix, previous, tag );
	}
	
	return 0;
}

unsigned int get_graph ( unsigned int no_lines, bool **edge_existance, int **adjacency_matrix )
{
	unsigned int a[2][MAX_NO_OF_LINES][MAX_NO_OF_LINES];
	
	unsigned int ct_state = 1;
	
	unsigned int i, j, max = 0;
	for ( i = 0; i < no_lines; i++ )
	{
		for ( j = 0; j <= i; j++ )
		{
			scanf ( "%u", &a[0][i][j] );
			a[1][i][j] = ct_state++;
			
			if ( a[0][i][j] > max )
				max = a[0][i][j];
		}
	}
	
	for ( i = 0; i < no_lines; i++ )
	{
		for ( j = 0; j <= i; j++ )
		{
			a[0][i][j] = max - a[0][i][j];
		}
	}
	
	
	
	edge_existance[0][1] = true;
	adjacency_matrix[0][1] = a[0][0][0];
	for ( i = 0; i < no_lines-1; i++ )
	{
		for ( j = 0; j <= i; j++ )
		{
			edge_existance [ a[1][i][j] ] [ a[1][i+1][j] ] = true;
			adjacency_matrix [ a[1][i][j] ] [ a[1][i+1][j] ] = a[0][i+1][j];
			
			edge_existance [ a[1][i][j] ] [ a[1][i+1][j+1] ] = true;
			adjacency_matrix [ a[1][i][j] ] [ a[1][i+1][j+1] ] = a[0][i+1][j+1];
		}
	}
	
	return max;
	
}

unsigned int get_max_length ( unsigned int no_lines, int **adjacency_matrix, int *tag, unsigned int *previous, unsigned int offset )
{
	unsigned int start = ( ( (no_lines-1) * ( (no_lines-1) + 1 ) ) / 2 ) + 1;
	
	
	int min_node = start, min = tag[start];
	unsigned int i;
	for ( i = start+1; i < start + (no_lines-1); i++ )
	{
		if ( tag[i] < min )
		{
			min = tag[i];
			min_node = i;
		}
	}
	
	unsigned int sum = 0;
	i = min_node;
	while ( i != 0 )
	{	
		//printf ( "%d - %d : %d \n", previous[i], i, ( offset - adjacency_matrix[previous[i]][i] ) );
		sum += ( offset - adjacency_matrix[previous[i]][i] );
		i = previous[i];
	}
	
	return sum;
}



And this is "dijkstra.h"

#include <stdbool.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

int dijkstra_allocate ( unsigned int, bool ***, int ***, unsigned int **, int ** );

bool dijkstra_deallocate ( unsigned int, bool **, int **, unsigned int *, int * );

int dijkstra ( unsigned int, bool **, int **, unsigned int *, int * );

bool all ( bool *, unsigned int, bool );

unsigned int extract_min ( bool *, unsigned int, int * );

void relax ( int *, unsigned int, unsigned int, bool **, int **, unsigned int * );

int dijkstra_allocate ( unsigned int no_nodes, bool ***edge_existance, int ***adjacency_matrix, unsigned int **previous , int **tag)
{
	if ( no_nodes == 0 )
	{
		fprintf ( stderr, "Fa773N M0nK, Dijkstra : 	Number of Nodes is given as zero. What happened? Did the graph fuck itself?" );
		return 1;
	}
	
	*edge_existance = malloc ( no_nodes * sizeof( bool * ) );
	if ( *edge_existance == NULL )
	{
		fprintf ( stderr, "Fa773N M0nK, Dijkstra : 	malloc() failed!" );
		return 2;
	}
	unsigned int i;
	for ( i = 0; i < no_nodes; i++ )
	{
		(*edge_existance)[i] = malloc ( no_nodes * sizeof(bool) );
		if ( (*edge_existance)[i] == NULL )
		{
			fprintf ( stderr, "Fa773N M0nK, Dijkstra : 	malloc() failed!" );
			return 2;
		}
	}
	
	
	*adjacency_matrix = malloc ( no_nodes * sizeof( int * ) );
	for ( i = 0; i < no_nodes; i++ )
	{
		(*adjacency_matrix)[i] = malloc ( no_nodes * sizeof(int) );
		if ( (*adjacency_matrix)[i] == NULL )
		{
			fprintf ( stderr, "Fa773N M0nK, Dijkstra : 	malloc() failed!" );
			return 2;
		}
	}
	
	(*previous) = malloc ( no_nodes * sizeof( unsigned int ) );
	if ( (*previous) == NULL )
	{
		fprintf ( stderr, "Fa773N M0nK, Dijkstra : 	malloc() failed!" );
		return 2;
	}
	
	(*tag) = malloc ( no_nodes * sizeof( int ) );
	if ( (*tag) == NULL )
	{
		fprintf ( stderr, "Fa773N M0nK, Dijkstra : 	malloc() failed!" );
		return 2;
	}
	for ( i = 0; i < no_nodes; i++ )
	{
		(*tag)[i] = INT_MAX;
	}
	
	return 0;
}

bool dijkstra_deallocate ( unsigned int no_nodes, bool **edge_existance, int **adjacency_matrix, unsigned int *previous, int *tag )
{
	unsigned int i;
	
	for (i = 0; i < no_nodes; i++)
	{
        free ( edge_existance[i] );
    }
    free ( edge_existance );
    
    for (i = 0; i < no_nodes; i++)
	{
        free ( adjacency_matrix[i] );
    }
    free ( adjacency_matrix );
    
    free ( previous );
    
	free ( tag );
    
    return true;

}

int dijkstra ( unsigned int no_nodes, bool **edge_existance, int **adjacency_matrix, unsigned int *previous, int *tag )
{
	bool *tested_status;
	
	tested_status = malloc ( no_nodes * sizeof(bool) );
	if ( tested_status == NULL )
	{
		fprintf ( stderr, "Fa773N M0nK, Dijkstra : 	malloc() failed!" );
		return 1;
	}

	unsigned int curr_node;

	tag[0] = 0;
	//tested_status[0] = true;
	while ( ! all ( tested_status, no_nodes, true ) )
	{
		curr_node = extract_min ( tested_status, no_nodes, tag );
		//printf ( "\n\rCurrent Smallest Node is %u\n", curr_node );

		relax ( tag, no_nodes, curr_node, edge_existance, adjacency_matrix, previous );

		tested_status[curr_node] = true;
	}
	
	free ( tested_status );
	free ( tag );
	
	return 1;
}

bool all ( bool *tested_status, unsigned int max, bool value )
{
	int i;

	for ( i = 0; i < max; i++ )
	{
		if ( tested_status[i] != value )	return false;
	}

	return true;
}

unsigned int extract_min ( bool *tested_status, unsigned int no_nodes, int *tag )
{
	unsigned int min = UINT_MAX, min_element;

	unsigned int i;
	for ( i = 0; i < no_nodes; i++ )
	{
		if ( tested_status[i] == false && tag[i] < min )
		{
			min = tag[i];
			min_element = i;
		}
	}


	if ( min == UINT_MAX )
	{
	    min_element = 0;
	}

	return min_element;
}

void relax ( int *tag, unsigned int no_nodes, unsigned int curr_node, bool **edge_existance, int **adjacency_matrix, unsigned int *previous )
{
	unsigned int i;
	for ( i = 0; i < no_nodes; i++ )
	{
		if ( edge_existance[curr_node][i] != false )
		{
			if ( ( tag[curr_node] + adjacency_matrix[curr_node][i] ) < tag[i] )
			{
				tag[i] = ( tag[curr_node] + adjacency_matrix[curr_node][i] );
				previous[i] = curr_node;
				
				//printf ( "\n\tprevious of %u set as the current node\n", i );
			}
		}
	}
}



Is This A Good Question/Topic? 0
  • +

Replies To: Segmentation Fault, free() and scanf()

#2 Salem_c  Icon User is online

  • void main'ers are DOOMED
  • member icon

Reputation: 1678
  • View blog
  • Posts: 3,180
  • Joined: 30-May 10

Re: Segmentation Fault, free() and scanf()

Posted 18 September 2012 - 11:54 AM

Well we could have managed without all the profanity in your error messages.

First, if you're using Linux, here's a handy tool.
$ valgrind ./a.out 
==3069== Memcheck, a memory error detector
==3069== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==3069== Using Valgrind-3.6.1-Debian and LibVEX; rerun with -h for copyright info
==3069== Command: ./a.out
==3069== 
1 
2
1 2 3
==3069== Conditional jump or move depends on uninitialised value(s)
==3069==    at 0x400AD4: all (foo.c:137)
==3069==    by 0x400A85: dijkstra (foo.c:115)
==3069==    by 0x400CE8: main (foo.c:218)
==3069== 
==3069== Conditional jump or move depends on uninitialised value(s)
==3069==    at 0x400B1E: extract_min (foo.c:150)
==3069==    by 0x400A3E: dijkstra (foo.c:117)
==3069==    by 0x400CE8: main (foo.c:218)
==3069== 
==3069== Conditional jump or move depends on uninitialised value(s)
==3069==    at 0x400BA5: relax (foo.c:171)
==3069==    by 0x400A65: dijkstra (foo.c:120)
==3069==    by 0x400CE8: main (foo.c:218)
==3069== 
==3069== Invalid read of size 4
==3069==    at 0x40121F: get_max_length (foo.c:282)
==3069==    by 0x400D04: main (foo.c:220)
==3069==  Address 0x51d03d8 is 8 bytes inside a block of size 16 free'd
==3069==    at 0x4C282E0: free (vg_replace_malloc.c:366)
==3069==    by 0x400AA4: dijkstra (foo.c:126)
==3069==    by 0x400CE8: main (foo.c:218)
==3069== 
3
==3069== Invalid free() / delete / delete[]
==3069==    at 0x4C282E0: free (vg_replace_malloc.c:366)
==3069==    by 0x4009B7: dijkstra_deallocate (foo.c:94)
==3069==    by 0x400D3B: main (foo.c:224)
==3069==  Address 0x51d03d0 is 0 bytes inside a block of size 16 free'd
==3069==    at 0x4C282E0: free (vg_replace_malloc.c:366)
==3069==    by 0x400AA4: dijkstra (foo.c:126)
==3069==    by 0x400CE8: main (foo.c:218)
==3069== 
==3069== 
==3069== HEAP SUMMARY:
==3069==     in use at exit: 0 bytes in 0 blocks
==3069==   total heap usage: 13 allocs, 14 frees, 180 bytes allocated
==3069== 
==3069== All heap blocks were freed -- no leaks are possible
==3069== 
==3069== For counts of detected and suppressed errors, rerun with: -v
==3069== Use --track-origins=yes to see where uninitialised values come from
==3069== ERROR SUMMARY: 29 errors from 5 contexts (suppressed: 4 from 4)


First problem seems to be that you're
- freeing tag in two places
- using it after you freed it.

The other problem seems to be that you're using <= in a for loop indexing arrays.
This is always suspect - it's worth checking.
Was This Post Helpful? 1
  • +
  • -

#3 jimblumberg  Icon User is offline

  • member icon


Reputation: 4075
  • View blog
  • Posts: 12,578
  • Joined: 25-December 09

Re: Segmentation Fault, free() and scanf()

Posted 18 September 2012 - 12:02 PM

Also it's considered bad practice to have code inside include files.

Jim
Was This Post Helpful? 1
  • +
  • -

#4 Fa773N M0nK  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 18-September 12

Re: Segmentation Fault, free() and scanf()

Posted 18 September 2012 - 08:24 PM

View PostSalem_c, on 19 September 2012 - 12:24 AM, said:

Well we could have managed without all the profanity in your error messages.

First, if you're using Linux, here's a handy tool.
$ valgrind ./a.out 
==3069== Memcheck, a memory error detector
==3069== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==3069== Using Valgrind-3.6.1-Debian and LibVEX; rerun with -h for copyright info
==3069== Command: ./a.out
==3069== 
1 
2
1 2 3
==3069== Conditional jump or move depends on uninitialised value(s)
==3069==    at 0x400AD4: all (foo.c:137)
==3069==    by 0x400A85: dijkstra (foo.c:115)
==3069==    by 0x400CE8: main (foo.c:218)
==3069== 
==3069== Conditional jump or move depends on uninitialised value(s)
==3069==    at 0x400B1E: extract_min (foo.c:150)
==3069==    by 0x400A3E: dijkstra (foo.c:117)
==3069==    by 0x400CE8: main (foo.c:218)
==3069== 
==3069== Conditional jump or move depends on uninitialised value(s)
==3069==    at 0x400BA5: relax (foo.c:171)
==3069==    by 0x400A65: dijkstra (foo.c:120)
==3069==    by 0x400CE8: main (foo.c:218)
==3069== 
==3069== Invalid read of size 4
==3069==    at 0x40121F: get_max_length (foo.c:282)
==3069==    by 0x400D04: main (foo.c:220)
==3069==  Address 0x51d03d8 is 8 bytes inside a block of size 16 free'd
==3069==    at 0x4C282E0: free (vg_replace_malloc.c:366)
==3069==    by 0x400AA4: dijkstra (foo.c:126)
==3069==    by 0x400CE8: main (foo.c:218)
==3069== 
3
==3069== Invalid free() / delete / delete[]
==3069==    at 0x4C282E0: free (vg_replace_malloc.c:366)
==3069==    by 0x4009B7: dijkstra_deallocate (foo.c:94)
==3069==    by 0x400D3B: main (foo.c:224)
==3069==  Address 0x51d03d0 is 0 bytes inside a block of size 16 free'd
==3069==    at 0x4C282E0: free (vg_replace_malloc.c:366)
==3069==    by 0x400AA4: dijkstra (foo.c:126)
==3069==    by 0x400CE8: main (foo.c:218)
==3069== 
==3069== 
==3069== HEAP SUMMARY:
==3069==     in use at exit: 0 bytes in 0 blocks
==3069==   total heap usage: 13 allocs, 14 frees, 180 bytes allocated
==3069== 
==3069== All heap blocks were freed -- no leaks are possible
==3069== 
==3069== For counts of detected and suppressed errors, rerun with: -v
==3069== Use --track-origins=yes to see where uninitialised values come from
==3069== ERROR SUMMARY: 29 errors from 5 contexts (suppressed: 4 from 4)


First problem seems to be that you're
- freeing tag in two places
- using it after you freed it.

The other problem seems to be that you're using <= in a for loop indexing arrays.
This is always suspect - it's worth checking.


Thanks a lot for the quick reply!

It WAS the tag which was creating the problem!
Once upon a time tag was just meant to be an internal variable. But, I later decided that it should show in the final result. So I put up its allocation and deallocation in the general allocate/deallocate functions, but sadly forgot to remove its deallocation from inside. :(


Also, I'm very sorry for the profanity! <insert a nightly build excuse here> :oops:

Again thanks!
Was This Post Helpful? 0
  • +
  • -

#5 Fa773N M0nK  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 18-September 12

Re: Segmentation Fault, free() and scanf()

Posted 18 September 2012 - 08:30 PM

View Postjimblumberg, on 19 September 2012 - 12:32 AM, said:

Also it's considered bad practice to have code inside include files.

Jim


Hey Jim!

I didn't know that :eek:

I am doing some reading on header files now (http://www.embedded.com/electronics-blogs/barr-code/4215934/What-belongs-in-a-header-file).


Thanks a lot for this info!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1