Speller Segmentation Fault Even After Freeing Malloc'd Nodes

Question

The following is my code and, subsequently, the message Valgrind returns when I run it on ./speller texts/lalaland.txt.

I explored similar issues previously posted on Stack exchange, and added lines to ensure that I was freeing any memory I had malloc'd. However, the exact same amount of memory continues to leak. Would massively appreciate some guidance on my code.

Thanks!

// Implements a dictionary's functionality
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include "dictionary.h"
#include <stdlib.h>

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

// TODO: Choose number of buckets in hash table
const unsigned int N = 26;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    int h = hash(word);
    if (table[h]->next != NULL)
    {
        node *ptr = table[h];
        while (ptr -> next != NULL)
        {
                if (strcmp(word, ptr -> word) == 0)
                {
                    return true;
                }
            ptr = ptr -> next;
        }
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    int first_letter = word[0];
    if(first_letter >= 65 && first_letter <= 90)
    {
        int hash_number = (first_letter - 65) % 26;
        return hash_number;
    }
    else if(first_letter >= 97 && first_letter <= 122)
    {
        int hash_number = (first_letter - 97) % 26;
        return hash_number;
    }
    return true;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        fclose(dict);
        return false;
    }

    char *word = malloc(46 * sizeof(char));

    while(fscanf(dict, "%s", word) != EOF)
    {
        fscanf(dict, "%s", word);
        node *tmp = malloc(sizeof(node));
        if (tmp == NULL)
        {
            free(tmp);
            free(word);
            return false;
        }
        strcpy(tmp->word, word);
        tmp = table[hash(word)]->next;
        table[hash(word)]->next = tmp;
            free(word);
            free(tmp);
    }
    free(dict);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    int counter = 0;
    for(int i = 0; i < N; i++)
    {
        if (table[i]->next != NULL)
        {
            node *ptr = table[i];
            if (table[i] != NULL)
            {
                while (ptr ->next != NULL)
                {
                    node *tmp = ptr->next;
                    ptr = tmp;
                    counter++;
                }
            }
        }
    }
    return counter;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TOD
    node *ptr = NULL;
    for(int i = 0; i < N; i++)
    {
        ptr = table[i];
        while(ptr->next != NULL)
        {
            free(table[i]);
            table[i] = ptr;
        }
    }
    free(ptr);
    return true;
}

speller/ $ valgrind ./speller texts/lalaland.txt
==5660== Memcheck, a memory error detector
==5660== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5660== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==5660== Command: ./speller texts/lalaland.txt
==5660== 
==5660== Invalid read of size 8
==5660==    at 0x109AF9: load (dictionary.c:85)
==5660==    by 0x1092BB: main (speller.c:40)
==5660==  Address 0x30 is not stack'd, malloc'd or (recently) free'd
==5660== 
==5660== 
==5660== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==5660==  Access not within mapped region at address 0x30
==5660==    at 0x109AF9: load (dictionary.c:85)
==5660==    by 0x1092BB: main (speller.c:40)
==5660==  If you believe this happened as a result of a stack
==5660==  overflow in your program's main thread (unlikely but
==5660==  possible), you can try to increase the size of the
==5660==  main thread stack using the --main-stacksize= flag.
==5660==  The main thread stack size used in this run was 8388608.
==5660== 
==5660== HEAP SUMMARY:
==5660==     in use at exit: 4,670 bytes in 4 blocks
==5660==   total heap usage: 4 allocs, 0 frees, 4,670 bytes allocated
==5660== 
==5660== 46 bytes in 1 blocks are still reachable in loss record 1 of 4
==5660==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==5660==    by 0x109A66: load (dictionary.c:72)
==5660==    by 0x1092BB: main (speller.c:40)
==5660== 
==5660== 56 bytes in 1 blocks are still reachable in loss record 2 of 4
==5660==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==5660==    by 0x109AA9: load (dictionary.c:77)
==5660==    by 0x1092BB: main (speller.c:40)
==5660== 
==5660== 472 bytes in 1 blocks are still reachable in loss record 3 of 4
==5660==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==5660==    by 0x49C76CD: __fopen_internal (iofopen.c:65)
==5660==    by 0x49C76CD: fopen@@GLIBC_2.2.5 (iofopen.c:86)
==5660==    by 0x109A3B: load (dictionary.c:65)
==5660==    by 0x1092BB: main (speller.c:40)
==5660== 
==5660== 4,096 bytes in 1 blocks are still reachable in loss record 4 of 4
==5660==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==5660==    by 0x49C6C23: _IO_file_doallocate (filedoalloc.c:101)
==5660==    by 0x49D5D5F: _IO_doallocbuf (genops.c:347)
==5660==    by 0x49D4D5B: _IO_file_underflow@@GLIBC_2.2.5 (fileops.c:485)
==5660==    by 0x49D5E15: _IO_default_uflow (genops.c:362)
==5660==    by 0x49AB14F: __vfscanf_internal (vfscanf-internal.c:628)
==5660==    by 0x49AA29C: __isoc99_fscanf (isoc99_fscanf.c:30)
==5660==    by 0x109A80: load (dictionary.c:74)
==5660==    by 0x1092BB: main (speller.c:40)
==5660== 
==5660== LEAK SUMMARY:
==5660==    definitely lost: 0 bytes in 0 blocks
==5660==    indirectly lost: 0 bytes in 0 blocks
==5660==      possibly lost: 0 bytes in 0 blocks
==5660==    still reachable: 4,670 bytes in 4 blocks
==5660==         suppressed: 0 bytes in 0 blocks
==5660== 
==5660== For lists of detected and suppressed errors, rerun with: -s
==5660== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
/opt/cs50/bin/valgrind: line 11:  5660 Segmentation fault      (core dumped) /usr/bin/valgrind $*

Answer 1

I see a couple related issues. Let's look at the while loop in load().

char *word = malloc(46 * sizeof(char));

while(fscanf(dict, "%s", word) != EOF)
{
    fscanf(dict, "%s", word);
    node *tmp = malloc(sizeof(node));

//  ... (( removed code that is unrelated to problems. ))

    strcpy(tmp->word, word);
    tmp = table[hash(word)]->next;          // Line 85
    table[hash(word)]->next = tmp;   
        free(word);                         // Line 87
        free(tmp);
}

This code will fail on the first pass through the loop. On the first pass, table[anything] is NULL or at best, garbage data. Nothing has been assigned to it. So, when line 85 executes, there's no struct to put any data in. table[hash(word)]->next doesn't exist. That's the seg fault, but that's not really the problem. Its only a symptom.

The real problem is the overall logic of lines 85 and 86. It's inverted, more or less. Here's what it does. Line 85 tries to assign something that doesn't exist to tmp (as noted above). Even if it did, this is incorrect. First, it will store the address from table[hash(word)]->next in tmp (which is likely NULL), overwriting that newly created node's address currently in tmp to be lost (a memory leak on it's own). Then, line 86 will try to store that same content back into table[hash(word)]->next.

I'll try to explain it differently, without the use of NULL values. Say that before line 85 is executed, the current linked list is pointed to by A. Currently A->next points to node X. Now, the code creates node Z and stored it in tmp. Line 85 will copy the address of node X from A->next to tmp. Node Z still exists, but the address has been lost. Line 86 will then copy the address of node X from tmp back to A->next.

Basically, the code is written backwards. This is what it should look like.

    tmp->next = table[hash(word)];          // Line 85
    table[hash(word)] = tmp;  

But wait, there's more. ;-)

Lines 87 and 88 are a big problem.

        free(word);
        free(tmp);

Line 87, frees the memory for word. That means that on the second pass through the loop, results are unpredictable. Remember that word was malloc'd before the start of the loop. Once freed, that memory is available for any other memory allocations via malloc or a related command. Unfortunately, the address of that memory remains in the var word. C may or may not flag an error during execution. If it fails to flag it, that's worse. The program will still access that memory through the word pointer. If it writes something to word, it will overwrite that memory, which may have been reallocated to another variable and contain data used elsewhere in the program. This is the definition of unpredictable.

Instead, word should not be freed until the function is done loading the dictionary and is ready to return to the calling code. It only needs to be allocated once, just as you have done, but not freed until it is no longer needed.

The free(tmp) statement is a bigger problem. It will effectively release the memory for every node created. Keep this in mind. Multiple variables can point to the same address. That's fine within c programs. BUT, if a free statement is executed on any one of those variables, the memory is released and you get a similar scenario to what I described above. There should not be any execution of a free statement on the memory for any of the nodes created, not even at the end of the function. We're far from done with any of that memory, so it needs to be left as allocated and not freed.

Here's how the freeing of word and tmp are different. word is basically a temporary variable that is used only in load. It's contents are always written out to another location (the word element in a node). When load is done, all the data has been stored elsewhere and there's no further need of the memory allocated to word. On the other hand, tmp will always contain data that is used by other functions later in the program. Deleting or releasing any of the nodes stored in tmp will be catastrophic. When load ends, the variable pointer tmp itself will go out of scope and be destroyed, but all the memory allocated to it (all of the nodes) will have been transferred to the linked lists. There's no need to free tmp itself. It's just a variable that contains an address and will go away on it's own.

That should get you going again. Happy programming! ;-)

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