where is this memory leak?

Question

I have been making this dictionary "spell check" function for a while and have finally got it fully functional, except for a small error of having no idea as to where this memory leak is. When I run valgrind this comes up:

> ==793== Memcheck, a memory error detector
> ==793== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
> ==793== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
> ==793== Command: ./speller texts/cat.txt
> ==793== 
> 
> MISSPELLED WORDS
> 
> ==793== Conditional jump or move depends on uninitialised value(s)
> ==793==    at 0x520A60F: tolower (ctype.c:46)
> ==793==    by 0x4010E2: check (dictionary.c:37)
> ==793==    by 0x400CD9: main (speller.c:112)
> ==793==  Uninitialised value was created by a stack allocation
> ==793==    at 0x4008E4: main (speller.c:21)
> ==793== 
> ==793== Use of uninitialised value of size 8
> ==793==    at 0x520A623: tolower (ctype.c:46)
> ==793==    by 0x4010E2: check (dictionary.c:37)
> ==793==    by 0x400CD9: main (speller.c:112)
> ==793==  Uninitialised value was created by a stack allocation
> ==793==    at 0x4008E4: main (speller.c:21)
> ==793== 
> 
> WORDS MISSPELLED:     0 WORDS IN DICTIONARY:  143091 WORDS IN TEXT:   
> 6 TIME IN load:         1.44 TIME IN check:        0.05 TIME IN size: 
> 0.00 TIME IN unload:       0.19 TIME IN TOTAL:        1.69
> 
> ==793== 
> ==793== HEAP SUMMARY:
> ==793==     in use at exit: 552 bytes in 1 blocks
> ==793==   total heap usage: 143,096 allocs, 143,095 frees, 8,023,416 bytes allocated
> ==793== 
> ==793== 552 bytes in 1 blocks are still reachable in loss record 1 of 1
> ==793==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==793==    by 0x5258E49: __fopen_internal (iofopen.c:65)
> ==793==    by 0x5258E49: fopen@@GLIBC_2.2.5 (iofopen.c:89)
> ==793==    by 0x401211: load (dictionary.c:77)
> ==793==    by 0x4009B4: main (speller.c:40)
> ==793== 
> ==793== LEAK SUMMARY:
> ==793==    definitely lost: 0 bytes in 0 blocks
> ==793==    indirectly lost: 0 bytes in 0 blocks
> ==793==      possibly lost: 0 bytes in 0 blocks
> ==793==    still reachable: 552 bytes in 1 blocks
> ==793==         suppressed: 0 bytes in 0 blocks
> ==793== 
> ==793== For counts of detected and suppressed errors, rerun with: -v
> ==793== ERROR SUMMARY: 8 errors from 2 contexts (suppressed: 0 from 0)

Sorry for posting the entire memory message, however I am not sure which part of the Valgrind message has the location of the error.

Below is the C code in which the error is occurring, I am assuming it is in the load or unload function.

```C

//for the universal hash function
#define BASE 256

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

// Number of buckets in hash table
const unsigned int N = 676;

// Hash table
node *table[N];
int word_count = 0;

// Returns true if word is in dictionary else false
//Require a search funtion
bool check(const char *word)
{
    //change to lower case to compare
    char low[LENGTH + 1];
    
    for (int i = 0, n = strlen(word); i <= (n + 1); i++)
    {
        low[i] = tolower(word[i]);
    }
    
    int hashIndex = hash(low);
    for (node *tmp = table[hashIndex]; tmp != NULL; tmp = tmp->next)
    {
        
        if (strcasecmp(low, tmp->word) == 0)
        {
            return true;
        }
    }
    return false;
}

// Hashes word to a number
// the dividing hash function is one I cited from the yale.edu page http://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)HashTables.html having worked with.
unsigned int hash(const char *word)
{
    unsigned long m = 11;
    unsigned long h;
    unsigned const char *us;
    //ensure element value is >= 0 
    us = (unsigned const char *) word;

    h = 0;
    while(*us != '\0') 
    {
        h = (h * BASE + *us) % m;
        us++;
    } 
    return (h % N);
}

// Loads dictionary into memory, returning true if successful else false
//Bring the used sictionary to menu asap
bool load(const char *dictionary)
{
    
    // Open file and check file 
    FILE *file = fopen(dictionary, "r");
    if (!file)
    {
        return false;
    }
    
    
    //array declaration for fscanf to read into
    char word[LENGTH + 1];
    while (fscanf(file, "%s", word) == 1)
    {
        //Create node n = new node
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            printf("No memory for node\n");
            fclose(file);
            return false;
            
        }
        strcpy(n->word, word);
        
        //Hash the word
        int hashDigit = hash(word);
        //Insert into the beginning of the list
        if (table[hashDigit] == NULL)
        {
            table[hashDigit] = n;
            n->next = NULL;
        }
        else
        {
            n->next = table[hashDigit];
            table[hashDigit] = n;
        }
        word_count++;
    }
    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
//free the dictionary from memory asap
bool unload(void)
{
    //Loop to run through array
    for (int i = 0; i < N; i++)
    {
        //to target linked list
        while (table[i] != NULL)
        {
            node *tmp = table[i];
            table[i] = table[i]->next;
            free(tmp);
        }
    }
    
    return true;
}

As far as I can tell I have tried the free all of the memory in unload correctly and this is appearing from a "Conditional jump or move depends on uninitialized value(s)" on line 36, however I am not sure what this exactly means or how to go about fixing the issue.

I would love some advice on how to do this better.

Answer 1

I was having the same issue with the same problem (Week 5 of Harvard's CS50 course), but the answers above only got me half of the way there.

Eventually solved it by explicitly assigning the null terminator '\0' to the remaining characters of each word, like so:

    for (int i = 0; i < LENGTH + 1; i++) {
        low[i] = (i < strlen(word)) ? tolower(word[i]) : '\0';
    }

Answer 2

It leaks FILE* you got from fopen. fclose is missing.

This is where valgrind tells you that:

==793== 552 bytes in 1 blocks are still reachable in loss record 1 of 1
==793==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==793==    by 0x5258E49: __fopen_internal (iofopen.c:65)
==793==    by 0x5258E49: fopen@@GLIBC_2.2.5 (iofopen.c:89)
==793==    by 0x401211: load (dictionary.c:77)
==793==    by 0x4009B4: main (speller.c:40)

fopen eventually calls malloc to allocate that FILE which must be released with fclose that eventually calls free on that FILE*.

---

Conditional jump or move depends on uninitialised value warning is caused by:

for (int i = 0, n = strlen(word); i <= (n + 1); i++)
    low[i] = tolower(word[i]);

That loop reads one extra character past the zero terminator. It needs a fix: either i <= n or i < (n + 1).

Answer 3

You make a big array of pointers here

node *table[N];

But you never set that array to NULL.

Then you do all kinds of stuff on that array assuming it has been initialized.

Answer 4

> ==793== 552 bytes in 1 blocks are still reachable in loss record 1 of 1
> ==793==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==793==    by 0x5258E49: __fopen_internal (iofopen.c:65)
> ==793==    by 0x5258E49: fopen@@GLIBC_2.2.5 (iofopen.c:89)
> ==793==    by 0x401211: load (dictionary.c:77)
> ==793==    by 0x4009B4: main (speller.c:40)

The leak is coming from fopen because you aren't calling fclose.