Source
r/cs50•
Toast-

SPOILER - Small memory leak (Pset4 - Speller Trie)

Spoilerspeller

Spoiler - My dictionary.c is pasted below, do not look further if you haven't done the pset!

I've been trying to challenge myself with the harder psets and finally got stuck. I think that I've got load, size, and unload working properly in terms of logic, but there is a small memory leak that I can't seem to track down.

Judging by the amount of memory leaked, the most obvious choices here would be my pointers, but after a bunch of attempts I'm starting to come up blank. I think I'm freeing them, and if I try to add more code to do so valgrind yells at me for an improper free call.

Could anyone point me in the right direction? I've got a few helper vars printing at the end that show "Nodes: 299477 Freed: 299473 Leaked: 1"

Spoilers if you haven't done the pset, my full dictionary.c is below:

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dictionary.h"

// Represents number of children for each node in a trie
#define N 27

// Helper for readability
#define BETWEEN(value, min, max) (value <= max && value >= min)

// Represents a node in a trie
typedef struct node
{
    bool is_word;
    struct node *children[N];
}
node;

// Function templates
node *makenode();
void freemem(node *n, node *ptr);

// Represents a trie
node *root;

// Init globals
int wordcount = 0;
int nodes = 0;
int frees = 0;

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize trie
    root = makenode();
    node *ptr = makenode();

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1];

    // Insert words into trie
    while (fscanf(file, "%s", word) != EOF)
    {
        int j = strlen(word);
        int index;

        // Loop through single letters of each word
        for (int i = 0; i < j; i++)
        {
            int curr_char = word[i];

            // Find the index the char belongs at
            if (BETWEEN(curr_char, 97, 122))         // lowercase
            {
                index = word[i] - 'a';
            }

            else if (BETWEEN(curr_char, 65, 90))    // uppercase
            {
                index = word[i] - 'A';
            }

            else                                    // apostrophe (curr_char == 39)
            {
                index = N - 1;
            }

            // Start navigating through the trie
            if (i == 0) // Base case
            {
                ptr = root;
            }

            // Check for end of word
            if (i != j - 1)
            {
                if (!ptr->children[index])
                {
                    ptr->children[index] = makenode();
                }
                else
                {
                    ptr = ptr->children[index];
                }
            }
            // Signal end of word
            else
            {
                ptr->is_word = true;
            }
        }
        wordcount++;
    }

    // Close dictionary
    fclose(file);

    free(ptr);
    frees++;

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    if (!wordcount)
    {
        return 0;
    }

    return wordcount;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Case insensitive
    // Only a-z or ' strings
    // if char == NULL, not a word
    // if you reach the end of the word, check the bool
    // TODO
    /*


    */


    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    node *ptr = makenode();
    freemem(root, ptr);
    printf("Nodes: %i Freed: %i Leaked: %i\n", nodes, frees, nodes - frees);
    return false;
}

// Helper fn to create and return a node
node *makenode()
{
    nodes++;
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return false;
    }

    n->is_word = false;
    for (int i = 0; i < N; i++)
    {
        n->children[i] = NULL;
    }
    return n;
}

void freemem(node *n, node *ptr)
{
    /*  Init point to n. For all of n's children, if != NULL
        then recursively pass that child into this function.
        Once all children are taken care of, free ptr.
    */
    ptr = n;
    for (int i = 0; i < N; i++)
    {
        if (ptr->children[i] != NULL)
        {
            freemem(n->children[i], ptr);
        }

    }
    free(ptr);
    frees++;


}

And valgrind log:

$ valgrind ./speller texts/cat.txt                                                                                                                       
==1543== Memcheck, a memory error detector
==1543== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==1543== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==1543== Command: ./speller texts/cat.txt
==1543== 

MISSPELLED WORDS

A
cat
is
not
a
caterpillar
==1543== Invalid read of size 8
==1543==    at 0x42AA2C: freemem (dictionary.c:183)
==1543==    by 0x42ABB7: freemem (dictionary.c:185)
==1543==    by 0x42ABB7: freemem (dictionary.c:185)
==1543==    by 0x42ABB7: freemem (dictionary.c:185)
==1543==    by 0x42A7D1: unload (dictionary.c:151)
==1543==    by 0x42900B: main (speller.c:152)
==1543==  Address 0xb050208 is 8 bytes inside a block of size 224 free'd
==1543==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1543==    by 0x42A737: load (dictionary.c:111)
==1543==    by 0x428202: main (speller.c:40)
==1543==  Block was alloc'd at
==1543==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1543==    by 0x42ACE1: makenode (dictionary.c:160)
==1543==    by 0x42A2AB: load (dictionary.c:92)
==1543==    by 0x428202: main (speller.c:40)
==1543== 
==1543== Invalid read of size 8
==1543==    at 0x42ABAC: freemem (dictionary.c:185)
==1543==    by 0x42ABB7: freemem (dictionary.c:185)
==1543==    by 0x42ABB7: freemem (dictionary.c:185)
==1543==    by 0x42ABB7: freemem (dictionary.c:185)
==1543==    by 0x42A7D1: unload (dictionary.c:151)
==1543==    by 0x42900B: main (speller.c:152)
==1543==  Address 0xb050228 is 40 bytes inside a block of size 224 free'd
==1543==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1543==    by 0x42A737: load (dictionary.c:111)
==1543==    by 0x428202: main (speller.c:40)
==1543==  Block was alloc'd at
==1543==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1543==    by 0x42ACE1: makenode (dictionary.c:160)
==1543==    by 0x42A2AB: load (dictionary.c:92)
==1543==    by 0x428202: main (speller.c:40)
==1543== 
==1543== Invalid free() / delete / delete[] / realloc()
==1543==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1543==    by 0x42AC19: freemem (dictionary.c:189)
==1543==    by 0x42ABB7: freemem (dictionary.c:185)
==1543==    by 0x42ABB7: freemem (dictionary.c:185)
==1543==    by 0x42ABB7: freemem (dictionary.c:185)
==1543==    by 0x42A7D1: unload (dictionary.c:151)
==1543==    by 0x42900B: main (speller.c:152)
==1543==  Address 0xb050200 is 0 bytes inside a block of size 224 free'd
==1543==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1543==    by 0x42A737: load (dictionary.c:111)
==1543==    by 0x428202: main (speller.c:40)
==1543==  Block was alloc'd at
==1543==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1543==    by 0x42ACE1: makenode (dictionary.c:160)
==1543==    by 0x42A2AB: load (dictionary.c:92)
==1543==    by 0x428202: main (speller.c:40)
==1543== 
Nodes: 299477 Freed: 299476 Leaked: 1
Could not unload dictionaries/large.
==1543== 
==1543== HEAP SUMMARY:
==1543==     in use at exit: 480 bytes in 3 blocks
==1543==   total heap usage: 299,483 allocs, 299,481 frees, 67,093,200 bytes allocated
==1543== 
==1543== 224 bytes in 1 blocks are definitely lost in loss record 2 of 3
==1543==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1543==    by 0x42ACE1: makenode (dictionary.c:160)
==1543==    by 0x429BE3: load (dictionary.c:41)
==1543==    by 0x428202: main (speller.c:40)
==1543== 
==1543== 224 bytes in 1 blocks are definitely lost in loss record 3 of 3
==1543==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1543==    by 0x42ACE1: makenode (dictionary.c:160)
==1543==    by 0x42A7BC: unload (dictionary.c:150)
==1543==    by 0x42900B: main (speller.c:152)
==1543== 
==1543== LEAK SUMMARY:
==1543==    definitely lost: 448 bytes in 2 blocks
==1543==    indirectly lost: 0 bytes in 0 blocks
==1543==      possibly lost: 0 bytes in 0 blocks
==1543==    still reachable: 32 bytes in 1 blocks
==1543==         suppressed: 0 bytes in 0 blocks
==1543== Reachable blocks (those to which a pointer was found) are not shown.
==1543== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==1543== 
==1543== For counts of detected and suppressed errors, rerun with: -v
==1543== ERROR SUMMARY: 33 errors from 5 contexts (suppressed: 0 from 0)

Posted Jul 14, 2019, 5:04 PM UTC

23
DarthWindu7•

The first thing you do in unload is create a new node. You then pass that pointer into freemen, where the first thing you do is set the variable to n. The original node created and pointed to by ptr is lost.

Also, I don't really think there's a need to pass in any pointer to freemem. The first thing you do is use the value in n; the value passed in is thrown away. I think you can just make ptr a local variable.

2
Toast-OP•

That makes sense.

I originally had a logic error in freemem that led to me making the ptr and it spun out of control a bit as one error would led into another.

I'll back up a bit and work through freemem again, thanks!

1
Toast-OP•

Got it! I removed the pointer from freemem like I originally had, so it looks like this now:

void freemem(node *n)
{
    for (int i = 0; i < N; i++)
    {
        if (n->children[i] != NULL)
        {
            freemem(n->children[i]);
        }
    }
    free(n);
}

And there was still one lurking issue, which I found in load. The ptr I was using there was being initialized withmakenode(), but then that node is never used, I just reassign the pointer. So, switching node *ptr = makenode(); to node *ptr; cleared up the last issue.

Thanks again!

1