segmentation fault again

[johndoe444]

Hi,

I thought I have mastered fighting segmentation fault thanks to the assistance of you guys. But still in this days I am getting seg fault. And there is no clue at all.

I am writing a suffix tree using a trie.

Here is the trace of segmentation fault:

aba n
abc y
bab n
bca y
cab y
abab n
0
just before malloc 52
just after malloc
1
just before malloc 52
just after malloc
just before malloc 52
just after malloc
2
just before malloc 52
just after malloc
just before malloc 52
just after malloc
3
just before malloc 52
just after malloc
just before malloc 52
just after malloc
4
just before malloc 52
just after malloc
just before malloc 52
just after malloc
[B]5
just before malloc 52
just after malloc
just before malloc 52

Program received signal SIGSEGV, Segmentation fault.
_int_malloc (av=0x7ffff7629e40, bytes=52) at malloc.c:4302
4302	malloc.c: No such file or directory.
	in malloc.c[/B]

No more clues given. The problemetic code is:

trie_node* create_node()
{	
	trie_node* node = (trie_node*) malloc(sizeof(trie_node));
	node->parent = NULL;
	node->is_leaf = 1;
	node->count_children = 0;

	node->children = (trie_node**) malloc(SIZE1*sizeof(trie_node*));

	for (int i = 0;i < SIZE1;i++)
	{
		node->children[i] = NULL;
	}

	node->edge = NULL;
	node->branch_at = 0;
	node->id = id_generator++;	
//	hash[node->id] = node;
	//printf("node->id %d(%p)\n",node->id, node);
	node->freq = 0;
	node->is_pruned = FALSE;
	node->key_index = -1;
	node->m = SIZE1;
	node->m1 = SIZE11;
[B]	printf("just before malloc %d\n", SIZE1*sizeof(int));
	node->hv = (int*) malloc(SIZE1*sizeof(int));
	printf("just after malloc\n");
[/B]	memset(node->hv, NIL, SIZE1*sizeof(int));

//	hash[count_nodes++] = node;

	return node;
}

I checked to see whether there can be duplicate places where the message is being printed:

lin309-05:~/workspace/acm$ grep just -n 10679.c 
116:	printf("just before malloc %d\n", SIZE1*sizeof(int));
118:	printf("just after malloc\n");
340:	// the case when the root node is null. so just create a new leaf and set the key

To release memory so that memory is not run out, after each operation when new suffix tree is created, the trie is destroyed:

void trie_destroy(trie_node** node)
{
	int i;
	trie_node* t_node = *node;
	free(t_node->hv);

	for (i = 0;i < t_node->m;i++)
	{
		if (t_node->children[i] != NULL)
		{
			trie_destroy(&(t_node->children[i]));
		}
	}

	t_node->edge = NULL;
	t_node->parent = NULL;

	free(t_node);
	*node = NULL;
}

char temp_str[1010];

int main()
{
	int i;
	int j;
	int nc;
	int nq;
	int t;

	freopen("in1.txt", "r", stdin);

	scanf("%d", &nc);
	for (t = 0;t < nc;t++)
	{
		....
		trie_destroy(&trie_root);
	}

	return 0;
}

The structure of the trie node is:

typedef struct _trie_node
{
	int key_index;
	int is_leaf;
	int count_children;
	int branch_at;
	struct _trie_node** children;
	struct _trie_node* edge;
	struct _trie_node* parent;
	int pos_in_parent;
	int id;
	int is_pruned;
	int freq;
	int* hv;
	int m;
	int m1;	
} trie_node;

SIZE1 is not that big:

#define ITEMS 53
#define SENTINEL '\0'
#define FALSE 0
#define SIZE1 13
#define SIZE11 11
#define SIZE2 23
#define SIZE22 19
#define SIZE3 53
#define SIZE33 47
#define MAX 100010

The sample for which the segmentation fault is occurring is this:

5 // number of test cases
aaa // string to generate suffices
6 // number of queries
a // query
aa // query
aaa // query
a // query
aa // query
aaa // query
abc // next string to generate suffices
6
a
b
c
ab
bc
abc // end of query
abcabab // string
6
aba
abc
bab
bca
cab
abab // end of query
aaabbb // string
6
ab
aabb
aaabbb
aabbb
abbb
bb // end of query
abbabba // string
6
ab
ba
abb
bba
abba
bbabb // end of query

Each time the 4th data set is processed there is seg fault. I tried to reshuffle the data sets. And each time whatever the dataset is the 4th one caused the seg fault.

So the data size (input) is very small ie only 7 characters at most. Each trie node is allocated only 13 children instead of 52 children. And between processing of 2 different datasets the previous trie is destroyed (memory released). Which means not too much memory is allocated. But still no clue why it seemingly encroached into the code segment. It gives no further indication.

With such little information it is like trying to find needle in the haystack. So any would be highly appreciated.

Thanks.

[UncleLeroy]

The problem is not the malloc() statement, but in some other code which is corrupting the heap (= the space owned by malloc()). I would run the code in the debugger, but I can't because it isn't complete; do that if you can.
If that isn't feasible, you can strip out some possible causes of error, and use debug rechniques.
Instead of free'ing your malloc space, just clear the pointer. It will leak, who cares during debugging.
Look carefully at the code which is not shown here, which is modifying the trie,
and even more carefully for any other code which is using malloc/free.
Another approach is to write a function to test the trie contents for corruption, and call it at various points in the "other code".
Some compilers offer library options to check the heap on every malloc/free, enable that option if you have it. Also look for a library function that checks the heap, call that often if your compiler has one.
You can temporarily hard-code the array sizes of *hv and **children as hv[SIZE1] and *children[SIZE1] to eliminate their malloc's and free's as possible causes.
Is it right that both are the same SIZE1?
Is the "other code" (not posted) using the same #define?
How about setting all your SIZE* definitions to the same value (for debugging only)?
And change all of them to one (1) (for debug only).

Sorry I can't help more, I can't look at (or run) the parts of the code which are not posted.