pset5 speller Memory Leak, if I free memory it breaks program

Question

I've got a problem with pset5 speller leaking memory. If I free that memory, it breaks my program when the check function is called with invalid reads of free'd memory. As you can see from my valgrind output before this is happening on dictionary.c:57, so char* w = malloc(sizeof(word));

If I call free(w) at the end of each iteration of the for loop in the load function, it breaks the program when check is called.

> ==2835== 
> ==2835== HEAP SUMMARY:
> ==2835==     in use at exit: 6,439,095 bytes in 143,091 blocks
> ==2835==   total heap usage: 286,184 allocs, 286,184 frees, 8,729,687 bytes allocated
> ==2835== 
> ==2835== 45 bytes in 1 blocks are still reachable in loss record 1 of 2
> ==2835==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==2835==    by 0x422A0D: load (dictionary.c:57)
> ==2835==    by 0x4209F2: main (speller.c:40)
> ==2835== 
> ==2835== 6,439,050 bytes in 143,090 blocks are definitely lost in loss record 2 of 2
> ==2835==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==2835==    by 0x422A0D: load (dictionary.c:57)
> ==2835==    by 0x4209F2: main (speller.c:40)
> ==2835== 
> ==2835== LEAK SUMMARY:
> ==2835==    definitely lost: 6,439,050 bytes in 143,090 blocks
> ==2835==    indirectly lost: 0 bytes in 0 blocks
> ==2835==      possibly lost: 0 bytes in 0 blocks
> ==2835==    still reachable: 45 bytes in 1 blocks
> ==2835==         suppressed: 0 bytes in 0 blocks
> ==2835==

code:

// Implements a dictionary's functionality

#include <stdbool.h>

#include "dictionary.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cs50.h>
#include <ctype.h>

typedef struct node
{
    char* w;
    struct node* next;
} node;

int loadedCount;
node* arr[26];

int hash(const char* word);

// Returns true if word is in dictionary else false
bool check(const char* word)
{
    // TODO
    char tmp[strlen(word) + 1];
    strcpy(tmp, word);

    for (int i = 0; i < strlen(tmp); i++)
    {
        tmp[i] = tolower(tmp[i]);
    }

    int index = hash(tmp);
    node* n = arr[index];
    while (n != NULL)
    {
        if (strcmp(n->w, tmp) == 0)
        {
            return true;
        }
        n = n->next;
    }
    return false;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{

    // TODO
    FILE* fp = fopen(dictionary, "r");
    char word[45];
    while (fscanf(fp, "%s", word) != EOF)
    {
        char* w = malloc(sizeof(word));
        strncpy(w, word, sizeof(word));
        int index = hash(word);
        node* n = malloc(sizeof(node));
        n->w = NULL;
        n->next = NULL;
        if (arr[index] != NULL)
        {
            n->next = arr[index];
        }
        n->w = w;
        arr[index] = n;
        loadedCount++;
    }
    fclose(fp);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    for (int i = 0; i < 26; i++)
    {
        node* n = arr[i];
        node* tmp = NULL;
        while (n != NULL)
        {
            tmp = n;
            n = n->next;
            free(tmp);
        }
    }

    return true;
}

int hash(const char* word)
{
    int n = word[0] - 'a';
    return n;
}

Answer 1

This isn't a solution as much as it is a clue and a pointer on what to do. Valgrind is telling you where the memory that is lost or still reachable has been allocated. It's not saying that this is the problem. What it means is that there's a problem on how it is freed (lost), or that it hasn't been freed (still reachable).

Testing with a small dictionary reveals an interesting fact. The number of lost blocks is equal to the number of words. That screams that there's a problem in unload().

Now, go back and look at the structure of a node.typedef struct node

{
    char* w;
    struct node* next;
} node;

->w is a pointer. It is populated by n->w = w; which is previously created by char* w = malloc(sizeof(word));.

Each call to unload frees a node, but w is only a pointer. The pointer is freed, but not the memory pointed at. When is the actual memory containing the word freed???? The attempts described break the program because the memory is still very much needed in load and in check.

This is pretty easily fixed in unload, but could also be fixed in load. When creating a node, the code is a bit more complex than necessary. The target word is copied into memory allocated to a local var, the address of which is then transferred to a new node. There's extensive initialization, etc.

Instead, why not simply create a new node, allocate the memory to it, and directly copy the word into it? This would eliminate the need for the char* w var and related code completely. Also, using a char array instead of a pointer would incorporate the memory for the word directly into the node so separate malloc and free would not be needed.

Finally, break the habit of using single letter vars now. They should never be used except as counters in small for loops. Use descriptive vars instead. They're a pain to maintain later in larger programs. Imagine trying to find every use of a variable 'w' or worse, 'e' or 's', in a 10,000 line program. Do a search on your current code and see how many finds you have that aren't actually the variable you seek!

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)