0

Could somebody help me identify the cause of the memory leak shown by Valgrind? Check50 says that there are no leaks, for some reason. Here is my code for dictionary.c

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Represents number of children for each node in a trie
#define N 27

// Represents a node in a trie
typedef struct node
{
    bool is_word;
    struct node *children[N];
}
node;

// Represents a trie
node *root;

unsigned int wordcount = 0;

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize trie
    root = malloc(sizeof(node));
    if (root == NULL)
    {
        return false;
    }
    root->is_word = false;
    for (int i = 0; i < N; i++)
    {
        root->children[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 trie
    while (fscanf(file, "%s", word) != EOF)
    {
        node *cursor = root;

        for (int i = 0; i < strlen(word); i++)
        {
            int letnum = (tolower(word[i]) - 'a' == '\'') ? 26 : ((int) tolower(word[i]) - 'a');

            if (cursor->children[letnum] == NULL)
            {
                node *n = malloc(sizeof(node));
                if (n == NULL)
                {
                    printf("malloc didn't work\n");
                    return false;
                }

                n->is_word = false;
                for (int j = 0; j < N; j++)
                {
                    n->children[j] = NULL;
                }

                cursor->children[letnum] = n;
                cursor = cursor->children[letnum];
            }
            else
            {
                cursor = cursor->children[letnum];
            }

        }
        cursor->is_word = true;
        wordcount ++;

    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

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

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    node *cursor = root;

    int wordlen = strlen(word);

    for (int i = 0; i < wordlen; i++)
    {
        int letnum = (tolower(word[i]) - 'a' == '\'') ? 26 : ((int) tolower(word[i]) - 'a');
        if (cursor->children[letnum] != NULL)
        {
            cursor = cursor->children[letnum];
            if (i == wordlen - 1 && cursor->is_word == true)
            {
                return true;
            }
        }
        else if (cursor->children[letnum] == NULL && i < wordlen - 1)
        {
            return false;
        }
    }

    return false;
}

void clearnode(node *trav);

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    node *trav = root;

    clearnode(trav);
    free(root);
    return true;
}

void clearnode(node *trav)
{
    for (int i = 0; i < N; i++)
    {
        if (trav->children[i] != NULL)
        {
            clearnode(trav->children[i]);
        }
        free(trav->children[i]);
    }
}

And the Valgrind output is below

~/pset5/speller/ $ valgrind ./speller texts/cat.txt
==8874== Memcheck, a memory error detector
==8874== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==8874== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==8874== Command: ./speller texts/cat.txt
==8874== 
==8874== Invalid read of size 8
==8874==    at 0x401147: load (dictionary.c:62)
==8874==    by 0x400914: main (speller.c:40)
==8874==  Address 0x622cf98 is 8 bytes before an unallocated block of size 64 in arena "client"
==8874== 
==8874== Invalid write of size 8
==8874==    at 0x4011CC: load (dictionary.c:77)
==8874==    by 0x400914: main (speller.c:40)
==8874==  Address 0x622cf98 is 8 bytes before an unallocated block of size 64 in arena "client"
==8874== 
==8874== Invalid read of size 8
==8874==    at 0x4011D9: load (dictionary.c:78)
==8874==    by 0x400914: main (speller.c:40)
==8874==  Address 0x622cf98 is 8 bytes before an unallocated block of size 64 in arena "client"
==8874== 

MISSPELLED WORDS


WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        6
TIME IN load:         3.11
TIME IN check:        0.00
TIME IN size:         0.00
TIME IN unload:       4.24
TIME IN TOTAL:        7.36

==8874== 
==8874== HEAP SUMMARY:
==8874==     in use at exit: 1,344 bytes in 6 blocks
==8874==   total heap usage: 365,376 allocs, 365,370 frees, 81,853,424 bytes allocated
==8874== 
==8874== 672 bytes in 3 blocks are indirectly lost in loss record 1 of 2
==8874==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8874==    by 0x40115C: load (dictionary.c:64)
==8874==    by 0x400914: main (speller.c:40)
==8874== 
==8874== 1,344 (672 direct, 672 indirect) bytes in 3 blocks are definitely lost in loss record 2 of 2
==8874==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8874==    by 0x40115C: load (dictionary.c:64)
==8874==    by 0x400914: main (speller.c:40)
==8874== 
==8874== LEAK SUMMARY:
==8874==    definitely lost: 672 bytes in 3 blocks
==8874==    indirectly lost: 672 bytes in 3 blocks
==8874==      possibly lost: 0 bytes in 0 blocks
==8874==    still reachable: 0 bytes in 0 blocks
==8874==         suppressed: 0 bytes in 0 blocks
==8874== 
==8874== For counts of detected and suppressed errors, rerun with: -v
==8874== ERROR SUMMARY: 10 errors from 4 contexts (suppressed: 0 from 0)

Thanks in advance! And if you need more info, please let me know.

  • Hi, is this some modified version of the original exercise? I can't take a grip at what it is supposed to do. In the load function you're allocating a new node for every letter of every word. I don't know if that is what you're meant to do. – Tritum Jun 4 at 5:54
  • @Tritum This PSET5 is from 2019. Last year we could choose between hashtables or tries. I'm trying to get both versions done. – roman465 Jun 4 at 19:31
0

It seems your code has more than one memory errors:

  1. run with large
  Memory access error: reading from the outside of a memory space; abort execution.
  # Reading 4 bytes from 0x905cddc will read undefined values.
  #
  # The memory-space-to-be-read (start:0x905cec0, size:112 bytes) is allocated at
  #    file:/dictionary.c::64, 27
  #
  #                               0x905cec0               0x905cf2f
  #                               +------------------------------+
  #                         ......| the memory-space-to-be-read  |
  #                               +------------------------------+
  #                         ^~~~~~~~~~
  # the read starts at 0x905cddc that is 228 bytes before the memory-space start.
  #
  # Stack trace (most recent call first) of the read.
  # [0]  file:/dictionary.c::62, 17
  # [1]  file:/speller.c::40, 19
  # [2]  [libc-start-main]
  1. run with small
  Memory access error: freeing a non-pointer; abort execution.
  # free 0x0, which does not point to a legit memory space.
  # Stack trace (most recent call first) of the error.
  # [0]  file:/musl-1.1.10/src/malloc/safe_malloc.c::93, 5
  # [1]  file:/dictionary.c::151, 9
  # [2]  file:/dictionary.c::138, 5
  # [3]  file:/speller.c::152, 21
  # [4]  [libc-start-main]

You can debug it with this link

| improve this answer | |
  • Thanks for your comment! I can't seem to figure out how to use that website though. When I press "debug" it starts loading and never finishes. Could you tell me how you got the result that you posted? – roman465 Jun 4 at 19:32
  • Sorry, it is still under development. You just click "Run", it will build your code and run "speller small lalaland.txt". You should be able to see the error. BTW, please sign in if you can because we can only support our users remotely if we know their email addresses. – stensal Jun 4 at 20:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .