Why is the memory allocated for the dictionary still reachable after unloading? CS50 Speller

Question

Looked all over the internet and haven't found anything that works for me but basically when I run valgrind on my program it says that there is 8,013,568 bytes that are still reachable.

==190== Memcheck, a memory error detector

==190== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.

==190== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info

==190== Command: ./speller texts/lalaland.txt

==190== 

MISSPELLED WORDS

==190== Invalid read of size 1

==190==    at 0x483F865: strcasecmp (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)

==190==    by 0x4019D0: check (dictionary.c:37)

==190==    by 0x4015FB: main (speller.c:113)

==190==  Address 0x2f06000002a10f00 is not stack'd, malloc'd or (recently) free'd

==190== 

==190== 

==190== Process terminating with default action of signal 11 (SIGSEGV)

==190==  General Protection Fault

==190==    at 0x483F865: strcasecmp (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)

==190==    by 0x4019D0: check (dictionary.c:37)

==190==    by 0x4015FB: main (speller.c:113)

==190== 

==190== HEAP SUMMARY:

==190==     in use at exit: 8,013,568 bytes in 143,092 blocks

==190==   total heap usage: 143,096 allocs, 4 frees, 8,023,256 bytes allocated

==190== 

==190== 472 bytes in 1 blocks are still reachable in loss record 1 of 2

==190==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)

==190==    by 0x4A27AAD: __fopen_internal (iofopen.c:65)

==190==    by 0x4A27AAD: fopen@@GLIBC_2.2.5 (iofopen.c:86)

==190==    by 0x401371: main (speller.c:55)

==190== 

==190== 8,013,096 bytes in 143,091 blocks are still reachable in loss record 2 of 2

==190==    at 0x483DD99: calloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)

==190==    by 0x401ABD: load (dictionary.c:74)

==190==    by 0x4012BE: main (speller.c:40)

==190== 

==190== LEAK SUMMARY:

==190==    definitely lost: 0 bytes in 0 blocks

==190==    indirectly lost: 0 bytes in 0 blocks

==190==      possibly lost: 0 bytes in 0 blocks

==190==    still reachable: 8,013,568 bytes in 143,092 blocks

==190==         suppressed: 0 bytes in 0 blocks

==190== 

==190== For lists of detected and suppressed errors, rerun with: -s

==190== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Segmentation fault

This is my code:

The hash function is just the lower case ascii value of the first character of the word as I wanted to just get my program working first before I worried about the hash function

// Implements a dictionary's functionality

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

#include "dictionary.h"


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

const unsigned int N = 4294967291;

unsigned int dictSize = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    unsigned int hn = hash(word);
    node *buffer = table[hn];

    while(buffer!=NULL)
    {
        if(strcasecmp(word, buffer->word)==0)
        {
            return true;
        }
        else
        {
            buffer = buffer->next;
        }
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    char x = tolower(word[0]);
    return (int)x;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *fp;
    fp = fopen(dictionary, "r");
    if(fp == NULL)
    {
        printf("Could not open file\n");
        return false;
    }
    char word[LENGTH + 1];

    int len;

    unsigned int hn;

    while(fscanf(fp, "%s", word) != EOF)
    {
        node *newNode = malloc(sizeof(node));
        if (newNode == NULL)
        {
            printf("Could not create new node\n");
            return false;
        }

        hn = hash(word);

        if(hn > N || hn < 0)
        {
            printf("Hash function acted improperly");
            return false;
        }

        strcpy(newNode->word, word);
        newNode->next = NULL;

        if(table[hn] == NULL)
        {
            table[hn] = newNode;
        }
        else
        {
            newNode->next = table[hn];
            table[hn] = newNode;
        }
        dictSize++;
    }
    fclose(fp);
    return true;
}

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

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

        while(next!=NULL)
        {
            node *buffer = next;
            next = next->next;
            free(buffer);
        }
        free(next);
        free(table[i]);
    }
    return true;
}

That dictionary size is downright absurd. That's **32GB** of just pointers. — tadman, Mar 24 '21 at 13:53
`free(table[i]);` - looks like double `free` to me here. You have already freed it by `next = table[i];`-> `buffer = next;` -> `free(buffer);` — Eugene Sh., Mar 24 '21 at 13:53
@PaulOgilvie That's okay, the program uses only the first 256 entries. (Look at the hash function.) The rest don't get paged in until unload(), where it also indexed off the end of the table. — Raymond Chen, Mar 24 '21 at 13:58

Antonin GAVREL · Answer 1 · 2021-03-24T14:10:32.790

0

You segfault because you are trying to allocate N bytes * sizeof(node) of bytes on the data segment (thanks Raymond Chen), which is way more than what a computer should be able to handle considering your N. Some Google results suggest 256kb is the limit.

const unsigned int N = 4294967291;

unsigned int dictSize = 0;

// Hash table
node *table[N];

Try again with malloc and it will be working (providing your program has no other error).

NB: You can check your current stack size with:

ulimit -a

You could set your data with unlimited and try again, but it would be a very bad solution for portability:

ulimit -d unlimited

edited Mar 24 '21 at 14:10

answered Mar 24 '21 at 13:55

Antonin GAVREL

9,682
8
54
81

Nope, that's a global variable, so it goes into bss. And [freeing a null pointer is legal and does nothing](https://stackoverflow.com/questions/1938735/does-freeptr-where-ptr-is-null-corrupt-memory) – Raymond Chen Mar 24 '21 at 13:58
1

Global variables (or more generally, variables with static storage duration) go into the static data segment. – Raymond Chen Mar 24 '21 at 14:01
I dont think the static data segment can handle 32Gb of data – Antonin GAVREL Mar 24 '21 at 14:02
Well somehow it did, seeing as the program compiled and ran according to OP. – Raymond Chen Mar 24 '21 at 14:45

Why is the memory allocated for the dictionary still reachable after unloading? CS50 Speller

1 Answers1