PSET5: Massive leak memory detected when using Valgrind, "Conditional jump or move depends on uninitialised value(s)"

Question

Before starting explaining my issue, I know there are threads talking about Conditional jump or move depends on uninitialised value(s) errors prompted after executing Valgrind but unfortunately, none of them helped me fixing my problems.

Also, I've already asked a question about this pset a few months ago, feel free to check it here as it fully described how I designed my code (I'll sum up the main parts of it below).

Long story short, I've done this pset a while ago, it works but I don't know why, I've totally skipped the Valgrind part... I'm currently revising all my psets before submitting them and well, when I came to verify pset5 and executed Valgrind, I had 9911860 errors reported... Not bad! :)

Last thing, I've read again and again these two threads:

Valgrind error in PSET6

valgrind messages about “unititialised value(s)” - are they an issue?

Both are treating Conditional jump or move depends on uninitialised value(s) issues and I'm sure I'm missing something very important over there, I've even posted a comment in the last one a few days ago but no answer came unfortunately.

OK so I've declared my node as it follows

//dictionary.h

typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

At the top of my dictionary.c sheet, I've declared as global variables

node* root;
node* newptr;

Later in the load function, I call root like this:

root = (struct node*) malloc(sizeof(node));
for (int i = 0; i < 27; i++)
{
    root->children[i] = NULL;
}

I've taken the idea of the for loop from Kareem's answer in Valgrind error in PSET6 topic except I didn't write root**[i]**->children[i] = NULL; as I can't compile my code then, I need to replace -> by a dot... and my errors count sees a rise of 25 errors (9911860)! Removing the index to root helped me to reduce the number of errors to 9911833, a 27 errors drop that totally makes sense to me.

Later in the load function, I declare newptr to be the next nodes in my trie:

node* newptr = (struct node*) malloc(sizeof(node));

This declaration comes in the loop that iterates through each character in the dictionary, inside the if statement checking if the end of the word in the dictionary has been reached.

If I apply the same method of initialization used for root, something like this for instance

node* newptr = (struct node*) malloc(sizeof(node));
for (int i = 0; i < 27; i++)
{
    newptr->children[i] = NULL;
}

The errors count doesn't drop.

Talking about newptr, I use this node as it follows:

if (isalpha(letter))
{
    if (newptr->children[letter - 'a'] == NULL)
    {
        newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node));
    }
    newptr = newptr->children[letter - 'a'];
}

Valgrind points out every lines like if (newptr->children[word[i] - 'a' == NULL) and newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node)); to be the source of the errors. Even the declaration of the node newptr itself is identified as an error.

If I pull this loop

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

or this

newptr->children[word[i] - 'a'];

before

newptr = newptr->children[letter - 'a'];

my errors count collapses to 2 or 3 errors but my code can't compile anymore due to a Segmentation Fault (core dumped).

Can someone please help me or at least explain me why the "NULL initialization loop" works for the root node but never works for the newptr node.

If more pseudo or chunks of my code are needed to understand my problem, please tell me and I'll edit my question.

Answer 1

First of all, I highly recommend you to read this thread: https://www.reddit.com/r/cs50/comments/3r0zb0/memorysegmentation_problems_with_dictionaryc_and/

I have done two major errors, I'll divide my answer in two parts for more clarity (well, I hope so!).

1. Setting nodes to NULL or false using memset()

In this thread, they talk about using memset() to set memory to false and NULL depending which line of the node (0 in memset() can mean both NULL and false).

In my load function, I've malloc'ed root = malloc(sizeof(node)); and that's it. If you use memset like this:

root = malloc(sizeof(node));
memset(root, 0, sizeof(node));

It will set your root node into something like this:

root->is_word = false;
root->children[27] = {NULL};

And that's exactly what we need to stop leaking memory! memset() must be used everytime you use malloc() to make sure everything is set to NULL or false. That means, you have to use it also in your loop, everytime you malloc a newptr...

This loop I was using

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

is ineffective and must be replaced by a memset().

2. Declaring newptr correctly

In her first comment, Irene (thank you for your help) underlined the undefined roles that root and newptr were playing in my code. Both are global variables but their use were unclear and indeed, newptr wasn't used properly.

In my load function, I first call root to malloc() and memset() it. Once the root of my trie correctly set, I open a first loop to get each character in the dictionary before loading the first word into my trie thanks to a second loop. In between, I was declaring newptr exactly how I declared root before the first loop iterating through the dictionary:

newptr = malloc(sizeof(node));
memset(newptr, 0, sizeof(node));

After adding all the memset() after all the malloc() in my load function, Valgrind was only pointing two errors, both coming from my newptr declaration.

When I loop through the first word read from the dictionary to store it in my trie, I first stores the first letter in my root node, then the second letter in a newptr node, the third in another newptr node and so on. At the end of the day, there are multiple newptr nodes, all descending from the root node of my trie.

If in every possible cases, that is to say:

 if (root->children[i] == NULL) // letter never stored in the root node
 if (newptr->children[i] == NULL) // letter never stored in the given newptr node
 if (newptr->children[26] == NULL) // apostrophe case

you correctly malloc() and memset() the next node of your trie, you don't need to do it before iterating through each word read from the dictionary! So getting a rid of

newptr = malloc(sizeof(node));
memset(newptr, 0, sizeof(node));

will help you to fix the last one or two errors remaining and stop leaking memory once for all.

I really hope this thread and my answer (I've tried to explain what I've understood) will help somebody, pset5 is in my opinion the second most difficult pset in CS50, right after resize from hacker4!

Good luck :)