PSET5 Valgrind memory leak in load() and errors in many contexts

Question

I'm trying to implement a trie for pset5. The program compiles, and appears to spit out the right output, except Valgrind seems to have a LOT of issues with it! First, there's the memory leak, which seems to be a product of something wrong in my load() code. Then, there's the ERROR SUMMARY which seems to be related to the issue in load(). Running Valgrind again with -v shows that the errors all seem to be stemming from the same place.

==11941== HEAP SUMMARY:
==11941==     in use at exit: 3,865,120 bytes in 17,255 blocks
==11941==   total heap usage: 367,084 allocs, 349,829 frees, 82,227,504 bytes allocated
==11941== 
==11941== 3,865,120 (1,916,768 direct, 1,948,352 indirect) bytes in 8,557 blocks are definitely lost in loss record 2 of 2
==11941==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11941==    by 0x40114B: load (dictionary.c:48)
==11941==    by 0x4008CD: main (speller.c:45)
==11941== 
==11941== LEAK SUMMARY:
==11941==    definitely lost: 1,916,768 bytes in 8,557 blocks
==11941==    indirectly lost: 1,948,352 bytes in 8,698 blocks
==11941==      possibly lost: 0 bytes in 0 blocks
==11941==    still reachable: 0 bytes in 0 blocks
==11941==         suppressed: 0 bytes in 0 blocks
==11941== 
==11941== For counts of detected and suppressed errors, rerun with: -v
==11941== ERROR SUMMARY: 27101 errors from 6 contexts (suppressed: 0 from 0)

These are the initializations I have in dictionary.h, if it matters:

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

node* root;
node* cursor;
int words_in_trie;

Here is my load() function, which Valgrind claims is causing an issue when I calloc memory for a new_node. I have tried to free(new_node) in several locations in my load() body, but there would always be some problem or another. I did manage to get all the memory leaks out when I added free(new_node) in the place where I've commented it in below, but when compiling and executing this, I always get a segmentation fault. Also, the number of errrors skyrockets. Please tell me what's wrong! I've been searching the forums for ages, and I really can't figure it out...

bool load(const char* dictionary)
{
    // open dictionary
    FILE* dict = fopen(dictionary, "r");
    if (dict == NULL)
        return false;

    // start up the trie
    root = calloc(1, sizeof(node));
    cursor = root;
    node* new_node = NULL;

    //take one char from dictionary at a time
    //put into trie
    // when encounter \n, is_word becomes true
    for (int c = fgetc(dict), position; c != EOF; c = fgetc(dict))
    {
        if (isalpha(c) || c == '\'')
        {
            if (isalpha(c))
                position = c - 'a';
            else
                position = 27;

            // if there's no open nodes, make new node for c
            if (cursor->children[position] == NULL)
            {
                new_node = calloc(1, sizeof(node));
                if (new_node == NULL)
                {
                    printf("Out of space for new nodes.\n");
                    return false;
                }

                cursor->children[position] = new_node;
                //free(new_node);
            }

            // update cursor
            cursor = cursor->children[position];
        }

        else
        {
            cursor->is_word = true;
            words_in_trie++;
            cursor = root;
        }
    }

    //check for file errors
    if (ferror(dict))
    {
        fclose(dict);
        printf("Error reading dictionary file");
        unload();
        return false;
    }

    //close file and return
    fclose(dict);
    return true;
}

I just know Valgrind is upset with my callocing, but I thought I had gotten rid of all that with my unload() -- which, if you were curious, looksl like this:

/**
 * helper function for unload
 */
void free_trie(node* cursor)
{
    for (int i = 0; i < 27; i++)
    {
        if (cursor->children[i] != NULL)
            free_trie(cursor->children[i]);
    }

    free(cursor);
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    free_trie(root);
    return true;
}

Please let me know if you know what's wrong with the code I spat out -- and thanks in advance!

Answer 1

You can't free nodes in load() because you need them to persist for the life of the program.

The recursive calls to free_trie() are running out of stack memory. From this post answer 1:

Each time you call a function, a certain amount of stack is eaten (usually dependent on the function). The eaten amount is the stack frame, and it is recovered when the function returns.

Here's another interesting post on the topic.

The small dictionary will do 11 calls to free_trie() before it does it's first free. That can stack up pretty quick in the large dictionary.

---

Does valgrind mention any invalid read/write? Another leak-waiting-to happen is here: position = 27;. According to your node definition (struct node* children[27];) children[27] is not allocated. Depending on dictionary, that's a segfault-waiting-to-happen too.