C - valgrind - invalid read of size 1

Question

I'm having some trouble debugging my code using Valgrind. Here is the structure and main part where the errors appear:

struct trieNode {
    char *word;
    struct trieNode *(subNode[LEAF_NUM]);
    struct sharpNode *sharp;    
};


//linked list of sharp(s)
struct sharpNode {
    char *word;
    struct sharpNode *next;
}; 

if (head->word == NULL){ 
    //strlen(head->word) == 0){
    head->word = (char *)malloc(MAX_LEN * sizeof(char));     //LINE 191
    //memset(head->word, '\0',strlen(head->word));
    strncpy (head->word, word, strlen(word));

} else { 

    if (head->sharp == NULL) {
        head->sharp = sharpNodeCreate();
        head->sharp->word = (char *)malloc(MAX_LEN * sizeof(char));    //LINE 200
        //head->sharp->word[strlen(word)] = '\0';
        strncpy (head->sharp->word, word, strlen(word));
    }

}

            } else if ( sharpIndex == 0 && strlen(trie_ptr->word) > 0) {
                printf("%s\n", trie_ptr->word);         //LINE 135
            } else if (notSharp == 0 && sharp_ptr != NULL) {
                printf("%s\n", sharp_ptr->word);       //LINE 137
            }  else {
                printf("There are no more T9onyms\n");
            }

And when I run valgrind, it complains:

==20040== Invalid read of size 1
==20040==    at 0x4A09264: __GI_strlen (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20040==    by 0x334BC6DD2B: puts (in /usr/lib64/libc-2.17.so)
==20040==    by 0x400C2C: lookupTrie (trie.c:135)
==20040==    by 0x400905: main (t9.c:23)
==20040==  Address 0x4c4e2f4 is 0 bytes after a block of size 4 alloc'd
==20040==    at 0x4A06409: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20040==    by 0x400D6B: populateTrie (trie.c:191)
==20040==    by 0x4008F9: main (t9.c:22)
==20040== 
ace

Enter Key Sequence (or "#" for next word):
#
==20040== Invalid read of size 1
==20040==    at 0x4A09264: __GI_strlen (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20040==    by 0x334BC6DD2B: puts (in /usr/lib64/libc-2.17.so)
==20040==    by 0x400C4A: lookupTrie (trie.c:137)
==20040==    by 0x400905: main (t9.c:23)
==20040==  Address 0x4dad294 is 0 bytes after a block of size 4 alloc'd
==20040==    at 0x4A06409: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20040==    by 0x400DDA: populateTrie (trie.c:200)
==20040==    by 0x4008F9: main (t9.c:22)

Can someone point me in the right direction?

Answer 1

The error you're getting is due to

strncpy (head->word, word, strlen(word));

and

strncpy (head->sharp->word, word, strlen(word));

not terminating their targets with NUL characters. strncpy() does not always NUL-terminate its output string; Indeed, it will only do so if word is shorter (in # of characters) than strncpy()'s size-argument.

Therefore, at run-time and with your current source string and size-argument to strncpy() (where the number of characters in the word is precisely equal to and not shorter than the size-argument), a NUL character is not written by strncpy() at the end of head->word. But when printf tries to print your string, it must implicitly find the end of that string, marked by its terminating NUL character. So it reads through all of the buffer you allocated failing to find a NUL character, and purely by luck finds one right after the end of the buffer, thus not crashing. Nevertheless this is an invalid read; Valgrind found it for you, but you must fix it.

To fix it, I suggest that you replace the size-argument of strncpy() with MAX_LEN-1, and that you manually terminate the string copy with head->word[MAX_LEN-1] = '\0'.

Alternately you can do as I have done before and implement yourself a strzcpy(char* d, char* s, size_t len) function that copies len-1 characters and NUL-terminates. It is a shame that such a function wasn't standardized until C11.

Answer 2

 strncpy (head->word, word, strlen(word));

Aside: this is not the first time I'm seeing this pattern. How does it manage to propagate itself? Bearers of this meme should have all been killed by natural selection already (if only...)

strncpy was invented to prevent buffer overflows. A buffer is the first argument of the function (where you stuff your data). An overflow happens when you try to stuff more data than it can hold. To prevent this, you limit the amount of data you can stuff in it by telling strncpy HOW MUCH DATA THE BUFFER IS ABLE TO HOLD. You pass in THE SIZE OF THE BUFFER. You don't pass how much data you have to copy. strncpy is perfectly able to figure it out itself. It cannot know how much data is safe to copy. THAT'S WHY YOU NEED TO PASS THAT AMOUNT TO IT IN A SEPARATE ARGUMENT.

And of course you must null-terminate your strings. strncpy won't do it for you if you make it fill your buffer to the brim.