Memory leak: blocks are still reachable - How to solve it?

Question

I have found some similar topics here: Valgrind - blocks still reachable due to? or here: Still Reachable Leak detected by Valgrind but none provided a solution. Hence, I want to raise this question again.

This is the result from valgrind:

==403== HEAP SUMMARY:
==403==     in use at exit: 7,791,056 bytes in 139,126 blocks
==403==   total heap usage: 143,096 allocs, 3,970 frees, 8,023,256 bytes allocated
==403== 
==403== 7,791,056 bytes in 139,126 blocks are still reachable in loss record 1 of 1
==403==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==403==    by 0x401BBE: load (dictionary.c:121)

and this is the code where I allocate memory to a new node:

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

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// ADDITIONAL functions
bool free_list(node *w);
unsigned int numeric(char c);

// Number of buckets in hash table
const unsigned int N = 26 * 28 * 28;
// Initialize number of word count in dictionary
int word_count = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO: initiate a node before looping
    node *n = table[hash(word)];
    // Checks if malloc succeeded, returns false if not
    while (true)
    {
        if (n == NULL)
        {
            return false;
        }
        else if (strcasecmp(n->word, word) == 0)
        {
            return true;
        }
        else
        {
            n = n->next;
        }
    }
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO
    int ret;
    ret = tolower(word[0]) - 97 + 26 * numeric(word[1]);
    if (word[1] != '\0')
    {
        ret += 26 * 28 * numeric(word[2]);
    }
    return ret;
}

// ADDITION: Numeric char value
unsigned int numeric(char c)
{
    int ret;
    if (isalpha(c))
    {
        ret = (tolower(c) - 96);
    }
    else if (c == '\0')
    {
        ret = 0;
    }
    else
    {
        ret = 27;
    }
    return ret;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO: Open file
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Could not open dictionary.\n");
        return false;
    }

    //Initialize the list to be NULL
    for (int i = 0; i < N; i += 1)
    {
        table[i] = NULL;
    }

    // COPY words in dictionary to hash table
    char c;
    char tmp[LENGTH + 1];
    int index = 0;
    while (fread(&c, sizeof(char), 1, dict))
    {
        if (c != '\n')
        {
            tmp[index] = c;
            index += 1;
        }
        else // means this is a full word
        {
            // Terminate current word
            tmp[index] = '\0';

            // Put the word to the hash
            // allocate memory to a new node
            node *n = malloc(sizeof(node));
            // Checks if malloc succeeded, returns false if not
            if (n == NULL)
            {
                unload();
                return false;
            }
            // assign values to new node
            n->next = table[hash(tmp)];
            strcpy(n->word, tmp);

            // make the hash point to the new node
            table[hash(tmp)] = n;

            // Clear the tmp array for next word
            for (int i = 0; i < index + 1; i += 1)
            {
                tmp[index] = 0;
            }
            word_count += 1; //Increase word count for size function
            index = 0;
        }
    }
    fclose(dict);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    for (int i = 0; i < N; i += 1)
    {
        free_list(table[i]);
    }

    return true;
}

// Create free linked-list function
bool free_list(node *w)
{
    if (w == NULL)
    {
        return true;
    }
    else if (w->next == NULL)
    {
        free(w);

        return true;
    }
    else
    {
        free_list(w->next);
        return true;
    }

}

The the line 121 in which HEAP SUMMARY reported a problem is the malloc line for a new node, in load() function: node *n = malloc(sizeof(node));

Could you please tell me why it leads to a memory leakage and how I can fix the problem?

Answer 1

Your free function only free memory of last element :

bool free_list(node *w)
{
    if (w == NULL) // empty : no free
    {
        return true;
    }
    else if (w->next == NULL) // free last element 
    {
        free(w);
        return true;
    }
    else
    {
        free_list(w->next); // try to free next element but not current
        return true;
    }
}

Should be modified as :

bool free_list(node *w)
{
    if (w == NULL)
    {
        return true;
    }
    // free next elements
    if (w->next != NULL)
    {
        free_list(w->next);
    }
    // free current
    free(w);
    return true;
}