Invalid write Valgrind

[sanket]

Hello all,

I am trying to read in the contents of a file into the data structure
trie (http://en.wikipedia.org/wiki/Trie). The file contains word-
meaning pairs separated by '\t'. If a word has two different meaning,
the second meaning should be appended to the existing meaning with a
comma between the two. Here is the function that adds a word into the
trie.

int add_word(const char * word, char * translation)
{
unsigned i = 0;
int len = strlen(word);
unsigned index = 0;
int retval = 0;

struct s_trie_node * curr = proot;

for(i = 0; i < len; i++)
{
index = word;
if(curr->children[index] != NULL) curr = curr-

children[index];

else
{
curr->children[index] = new_node();
curr = curr->children[index];
retval++;
}
}

if(curr->translation == NULL)
{
int s = strlen(translation);
curr->translation = (char*)malloc((s+1) *
sizeof(char));
if(curr->translation == NULL){
printf("malloc failed\n");
exit(EXIT_FAILURE);
}
strcpy(curr->translation, translation);
}
else
{
char * t = curr->translation;
size_t newlen = strlen(translation) + strlen(curr-

translation) + 1;

curr->translation = (char*)realloc(curr->translation,
newlen);

printf("%s\n", curr->translation);
printf("%s\n", translation);

if(curr->translation != NULL) t = NULL;
else
{
printf("realloc fails\n");
curr->translation = t;
t = NULL;
}

strcat(curr->translation, ",");
strcat(curr->translation, translation);
}

return retval;
}


Here are the contents of the file to read in from

Adam and Eve Adam et Eve
Albanian albanais
Albanian Albanais
Adam Adam
Adam Adamo

The program leads to memory error. When I execute the program using
Valgrind with memcheck option, I notice that when the second meaning
of a word is encountered and is appended to the existing meaning with
a comma in between, I receive the following error.

==1356== Invalid write of size 1
==1356== at 0x4C224DF: strcat (mc_replace_strmem.c:176)
==1356== by 0x400E65: add_word (prob2.c:147)
==1356== by 0x400F76: load_dictionary (prob2.c:185)
==1356== by 0x400AEA: main (prob2.c:44)
==1356== Address 0x51839b1 is 0 bytes after a block of size 17
alloc'd
==1356== at 0x4C215E2: realloc (vg_replace_malloc.c:525)
==1356== by 0x400DDE: add_word (prob2.c:133)
==1356== by 0x400F76: load_dictionary (prob2.c:185)
==1356== by 0x400AEA: main (prob2.c:44)


But the strange thing is that the error is encountered when second
meaning of the word 'Albanian' is added, though no such error is
encountered when the second meaning of 'Adam' is added. But if you
reverse them, then the error will be encountered with 'Adam' and not
'Albanian'. So, it seems that the word whose repetition is encountered
the first encounters the error.

Thanks.

 

[Harald van Dijk]

                size_t newlen = strlen(translation) + strlen(curr->translation) + 1;

                curr->translation = (char*)realloc(curr->translation,
newlen); [...]
                strcat(curr->translation, ",");
                strcat(curr->translation, translation);

You're writing strlen(curr->translation) + strlen(",") +
strlen(translation) + sizeof((char)'\0') bytes into curr->translation,
but newlen is one less than that. Depending on how realloc gets its
memory, this error may go undetected.