Speller hash table - unload memory not working

Question

Good afternoon

Hitting the last hurdle with unloading memory, can't figure where I'm going wrong

Code to load the hash table:

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize hash table
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = NULL;
    }

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

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

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL) // if malloc did not work
        {
            unload();
            return false;
        }
        else
        {
            strcpy(new_node->word, word);

            int first_letter_number = hash(word);

            // insert new_node at beginning of linked list
            new_node->next = hashtable[first_letter_number];
            hashtable[first_letter_number] = new_node;
            dict_word_count++;
        }
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    int nodes_freed = 0;
    int elements_freed = 0;

    // free the nodes
    for (int i = 0; i < N; i++)
    {
        for (node *ptr = hashtable[i]; ptr != NULL; ptr = ptr->next)
        {
            free(ptr);
            nodes_freed++;
        }
    }

    // free the hash table
    for (int i = 0; i < N; i++)
    {
        if (hashtable[i])
        {
            free(hashtable[i]);
            elements_freed = 0;
        }
    }

    printf("Number of nodes freed: %i\n", nodes_freed);
    printf("Number of hashtable elements freed: %i\n", elements_freed);

    return true;
}

My thinking for the unload is first to free all the nodes within the linked lists for each letter a..z

Then free each element in the array hashtable

Number of words in the dictionary is 143,091 and the number of nodes being freed is this exact number per printf above (number of hashtable elements freed is 0 so looks like they're all being cleared when freeing the nodes)

Valgrind log:

==9232== Memcheck, a memory error detector
==9232== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9232== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==9232== Command: ./speller ./texts/lalaland.txt
==9232== Parent PID: 187
==9232==
==9232== Invalid read of size 8
==9232==    at 0x401244: unload (dictionary.c:130)
==9232==    by 0x400E49: main (speller.c:153)
==9232==  Address 0x534b6a0 is 48 bytes inside a block of size 56 free'd
==9232==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9232==    by 0x40123F: unload (dictionary.c:132)
==9232==    by 0x400E49: main (speller.c:153)
==9232==  Block was alloc'd at
==9232==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9232==    by 0x40115E: load (dictionary.c:56)
==9232==    by 0x4009A4: main (speller.c:41)
==9232==
==9232== Invalid free() / delete / delete[] / realloc()
==9232==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9232==    by 0x40129B: unload (dictionary.c:141)
==9232==    by 0x400E49: main (speller.c:153)
==9232==  Address 0x534b670 is 0 bytes inside a block of size 56 free'd
==9232==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9232==    by 0x40123F: unload (dictionary.c:132)
==9232==    by 0x400E49: main (speller.c:153)
==9232==  Block was alloc'd at
==9232==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9232==    by 0x40115E: load (dictionary.c:56)
==9232==    by 0x4009A4: main (speller.c:41)
==9232==
==9232==
==9232== HEAP SUMMARY:
==9232==     in use at exit: 0 bytes in 0 blocks
==9232==   total heap usage: 143,096 allocs, 143,122 frees, 8,023,416 bytes allocated
==9232==
==9232== All heap blocks were freed -- no leaks are possible
==9232==
==9232== For counts of detected and suppressed errors, rerun with: -v
==9232== ERROR SUMMARY: 143117 errors from 2 contexts (suppressed: 0 from 0)

Any ideas?

Answer 1

Well, here's a really interesting scenario!

for (int i = 0; i < N; i++)
{
    for (node *ptr = hashtable[i]; ptr != NULL; ptr = ptr->next)
    {
        free(ptr);
        nodes_freed++;
    }
}

Think about what happens in this inner loop. The pointer is freed and the code comes back to the for loop line, where it increments by setting ptr = ptr->next. Think about that very carefully. ptr has been freed, but ptr->next is accessed after being freed. At best, I'd call this unpredictable behavior. Here's why. When ptr is freed, that memory is released to the system, but the contents of that memory isn't reset by this action. It just sits there until the memory is reallocated. Also, none of these pointers are reset to NULL when freed. The existing address remains in the pointer although the memory is released.

I think you've just been lucky. In a busy system, that memory could easily be allocated elsewhere and this could lead to either a seg fault or corruption. I'm amazed that this actually works! It is, however, leading to the invalid read of size 8 complaints in valgrind.

Simply put, you can't use a memory pointer's address contents once it's been freed. That's exactly what the code is trying to do when the for loop starts its next pass.

The invalid free() is much simpler. The addresses in the hashtable[i] array have already been freed by the prior nested for loops.

Amazingly though, it does free all the memory. But I don't know what would happen if some of the memory were to be reallocated while unload were running. My guess is that if the ptr address contents were modified (due to being reallocated) between being freed and the start of the next loop, it would lead to an invalid address and either throw a seg fault or lead to corruption.

A near-complete rewrite of unload() is in order. Some tips that will help:

1. try a while loop instead of a for loop. For loops are best used where a specific number of iterations are needed. While loops are best where a certain conditon (like a null pointer) is met.

2. Before deleting a node, store the address of the next node in a separate temporary pointer var so that you can access it.

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