2

I had posted a question here two days ago regarding memory leak in problem set 5 and haven't had it resolved yet. Please refer to my question, available here: CS50 PSET5 Memory Leak (please note that I had changed my code a little bit: my hash function is now

int index = ((int)(key[0]) - 'a') % 26;

instead of

int index = (toupper(key[0]) - 'A') % 26;

for that matters. After changing my hash function, it seems that less memories are leaked.

My speller seems to work fine, except that it fails to pass Valgrind. Attached below is the Valgrind report generated from this command:

valgrind --leak-check=full --show-leak-kinds=all -v ./speller

Please give me some guidelines to help me out of this 30+-hour long struggle. Thank you so much!

==1388== HEAP SUMMARY:
==1388==     in use at exit: 8,012,264 bytes in 143,067 blocks
==1388==   total heap usage: 143,094 allocs, 27 frees, 8,014,288 bytes allocated
==1388== 
==1388== Searching for pointers to 143,067 not-freed blocks
==1388== Checked 103,272 bytes
==1388== 
==1388== 568 bytes in 1 blocks are still reachable in loss record 1 of 4
==1388==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1388==    by 0x4EA537C: __fopen_internal (iofopen.c:73)
==1388==    by 0x40130E: load (dictionary.c:75)
==1388==    by 0x400A0D: main (speller.c:45)
==1388== 
==1388== 81,928 bytes in 1,463 blocks are possibly lost in loss record 2 of 4
==1388==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1388==    by 0x40136F: load (dictionary.c:86)
==1388==    by 0x400A0D: main (speller.c:45)
==1388== 
==1388== 7,928,256 bytes in 141,576 blocks are indirectly lost in loss record 3 of 4
==1388==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1388==    by 0x40136F: load (dictionary.c:86)
==1388==    by 0x400A0D: main (speller.c:45)
==1388== 
==1388== 7,929,768 (1,512 direct, 7,928,256 indirect) bytes in 27 blocks are definitely lost in loss record 4 of 4
==1388==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1388==    by 0x40136F: load (dictionary.c:86)
==1388==    by 0x400A0D: main (speller.c:45)
==1388== 
==1388== LEAK SUMMARY:
==1388==    definitely lost: 1,512 bytes in 27 blocks
==1388==    indirectly lost: 7,928,256 bytes in 141,576 blocks
==1388==      possibly lost: 81,928 bytes in 1,463 blocks
==1388==    still reachable: 568 bytes in 1 blocks
==1388==         suppressed: 0 bytes in 0 blocks
==1388== 
==1388== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
==1388== 
==1388== 1 errors in context 1 of 3:
==1388== Conditional jump or move depends on uninitialised value(s)
==1388==    at 0x4013A3: load (dictionary.c:93)
==1388==    by 0x400A0D: main (speller.c:45)
==1388==  Uninitialised value was created by a heap allocation
==1388==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1388==    by 0x40136F: load (dictionary.c:86)
==1388==    by 0x400A0D: main (speller.c:45)
==1388== 
==1388== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
1

I wanted to test your code so I took it from the link you provided.

When I tried to compile it, it did not compile. I had to fix two lines to get it to compile:

Line numbers are based on the code you provided:

Line 41 and 42:

char* small_cap = NULL;
char* small_cap malloc(sizeof(strlen(word)));

I did not understand why make it NULL if you were assigning an address later. Another thing I did not understand was the lack of an equal sign. So I changed those two to this line:

char* small_cap = malloc(sizeof(strlen(word)));

I had another error with line 61:

if(strcmp(cursor -> word_dict, *small_cap) == 0)

I don't think you want to pass the value of a character:

if pointer is a pointer to some variable, *pointer is the same as the value of the variable that the pointer is pointing to. For example:

int x = 5;
int* ptr = &x;

*ptr is equal to 5.

So I changed *small_cap and took the asterisk out. Meaning we are passing an array of characters, not a single character. The line looks like this:

if(strcmp(cursor -> word_dict, small_cap) == 0)

I got it to compile after those fixes. I ran the line you mention in this question:

valgrind --leak-check=full --show-leak-kinds=all -v ./speller

And valgrind gave me no errors.

I WAS USING VALGRIND WRONG, SEE LATEST UPDATE

  $ valgrind --leak-check=full --show-leak-kinds=all -v ./speller
 ==3054== Memcheck, a memory error detector
 ==3054== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
 ==3054== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
 ==3054== Command: ./speller
 ==3054== 
 --3054-- Valgrind options:
 --3054--    --leak-check=full
 --3054--    --show-leak-kinds=all
 --3054--    -v
 --3054-- Contents of /proc/version:
 --3054--   Linux version 4.2.0-c9 (root@b197fb11a5c1) (gcc version 4.9.2 (Debian 4.9.2-10) ) #2 SMP Thu Oct 20 09:52:05 UTC 2016
 --3054-- Arch and hwcaps: AMD64, amd64-cx16-lzcnt-rdtscp-sse3-avx-avx2-bmi
 --3054-- Page sizes: currently 4096, max supported 4096
 --3054-- Valgrind library directory: /usr/lib/valgrind
 --3054-- Reading syms from /home/ubuntu/workspace/help/pset5/AlexChan/pset5/speller
 --3054-- Reading syms from /lib/x86_64-linux-gnu/ld-2.19.so
 --3054--   Considering /lib/x86_64-linux-gnu/ld-2.19.so ..
 --3054--   .. CRC mismatch (computed 4cbae35e wanted 8d683c31)
 --3054--   Considering /usr/lib/debug/lib/x86_64-linux-gnu/ld-2.19.so ..
 --3054--   .. CRC is valid
 --3054-- Reading syms from /usr/lib/valgrind/memcheck-amd64-linux
 --3054--   Considering /usr/lib/valgrind/memcheck-amd64-linux ..
 --3054--   .. CRC mismatch (computed 37cdde19 wanted adc367dd)
 --3054--    object doesn't have a symbol table
 --3054--    object doesn't have a dynamic symbol table
 --3054-- Scheduler: using generic scheduler lock implementation.
 --3054-- Reading suppressions file: /usr/lib/valgrind/default.supp
 ==3054== embedded gdbserver: reading from /tmp/vgdb-pipe-from-vgdb-to-3054-by-ubuntu-on-???
 ==3054== embedded gdbserver: writing to   /tmp/vgdb-pipe-to-vgdb-from-3054-by-ubuntu-on-???
 ==3054== embedded gdbserver: shared mem   /tmp/vgdb-pipe-shared-mem-vgdb-3054-by-ubuntu-on-???
 ==3054== 
 ==3054== TO CONTROL THIS PROCESS USING vgdb (which you probably
 ==3054== don't want to do, unless you know exactly what you're doing,
 ==3054== or are doing some strange experiment):
 ==3054==   /usr/lib/valgrind/../../bin/vgdb --pid=3054 ...command...
 ==3054== 
 ==3054== TO DEBUG THIS PROCESS USING GDB: start GDB like this
 ==3054==   /path/to/gdb ./speller
 ==3054== and then give GDB the following command
 ==3054==   target remote | /usr/lib/valgrind/../../bin/vgdb --pid=3054
 ==3054== --pid is optional if only one valgrind process is running
 ==3054== 
 --3054-- REDIR: 0x4019ca0 (strlen) redirected to 0x38068331 (???)
 --3054-- Reading syms from /usr/lib/valgrind/vgpreload_core-amd64-linux.so
 --3054--   Considering /usr/lib/valgrind/vgpreload_core-amd64-linux.so ..
 --3054--   .. CRC mismatch (computed 329d6860 wanted c0186920)
 --3054--    object doesn't have a symbol table
 --3054-- Reading syms from /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so
 --3054--   Considering /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so ..
 --3054--   .. CRC mismatch (computed 1fb85af8 wanted 2e9e3c16)
 --3054--    object doesn't have a symbol table
 ==3054== WARNING: new redirection conflicts with existing -- ignoring it
 --3054--     old: 0x04019ca0 (strlen              ) R-> (0000.0) 0x38068331 ???
 --3054--     new: 0x04019ca0 (strlen              ) R-> (2007.0) 0x04c2e1a0 strlen
 --3054-- REDIR: 0x4019a50 (index) redirected to 0x4c2dd50 (index)
 --3054-- REDIR: 0x4019c70 (strcmp) redirected to 0x4c2f2f0 (strcmp)
 --3054-- REDIR: 0x401a9c0 (mempcpy) redirected to 0x4c31da0 (mempcpy)
 --3054-- Reading syms from /lib/x86_64-linux-gnu/libc-2.19.so
 --3054--   Considering /lib/x86_64-linux-gnu/libc-2.19.so ..
 --3054--   .. CRC mismatch (computed dc620abc wanted 148cbd6e)
 --3054--   Considering /usr/lib/debug/lib/x86_64-linux-gnu/libc-2.19.so ..
 --3054--   .. CRC is valid
 --3054-- REDIR: 0x4ec3d60 (strcasecmp) redirected to 0x4a25720 (_vgnU_ifunc_wrapper)
 --3054-- REDIR: 0x4ec6050 (strncasecmp) redirected to 0x4a25720 (_vgnU_ifunc_wrapper)
 --3054-- REDIR: 0x4ec3530 (memcpy@GLIBC_2.2.5) redirected to 0x4a25720 (_vgnU_ifunc_wrapper)
 --3054-- REDIR: 0x4ec17c0 (rindex) redirected to 0x4c2da30 (rindex)
 --3054-- REDIR: 0x4ecaac0 (strchrnul) redirected to 0x4c319b0 (strchrnul)
 Usage: speller [dictionary] text
 --3054-- REDIR: 0x4eb9df0 (free) redirected to 0x4c2bd80 (free)
 ==3054== 
 ==3054== HEAP SUMMARY:
 ==3054==     in use at exit: 0 bytes in 0 blocks
 ==3054==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
 ==3054== 
 ==3054== All heap blocks were freed -- no leaks are possible
 ==3054== 
 ==3054== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
 ==3054== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

This solves the memory issues but the program is not working correctly after those fixes.

I found one piece of code that might be causing errors. On lines 106-108:

           new_node -> next = head;
           head = new_node;
           word_count++;

The head does not get attached to the hashtables array as in the other case. I suggest you add this line to that block:

           hashtables[hash] = head;

I will look like this:

           new_node -> next = head;
           head = new_node;
           hashtables[hash] = head;
           word_count++;

After I added that line, check50 was giving all happy faces except for one: The case of pneumonoultramicroscopicsilicovolcanoconiosis. I did some gdb on it and found that when you are checking the word you save it successfully in an array called small_cap. When the program mallocs a new node for some reason I don't understand yet the array gets chopped from:

 small_cap = 0x603510 "pneumonoultramicroscopicsilicovolcanoconiosis"

to

 small_cap = 0x603510 "pneumonoultramicroscopicA"

That happens after this line executes:

      node* cursor = malloc(sizeof(node));

I have not been able to figure out why it does that. SEE UPDATE FOR SOLUTION ON THIS

FIRST UPDATE

I still don't know why small_cap gets chopped, but I found a solution.

Instead of declaring small_cap as a char* and mallocing it, you can declare as an array and make sure you NULL terminate it before doing operations with it:

Instead of:

char* small_cap = malloc(sizeof(strlen(word)));

do this:

char small_cap[LENGTH + 1];

and NULL terminate it after the loop. Like this:

char small_cap[LENGTH + 1];
for (int i = 0; i < (strlen(word)); i++)
{   
    if (isupper(word[i]))
        small_cap[i] = tolower(word[i]);
    else
        small_cap[i] = word[i];
}

small_cap[strlen(word)] = '\0';

SECOND UPDATE

I ran this valgrind command:

$ valgrind --leak-check=full --show-leak-kinds=all -v ./speller texts/austinpowers.txt

And just like you mentioned, there were errors and memory leaks. 3 errors to be specific.

I searched for all the mentions of the word malloc in my version of your code and I found it twice. The mention in the load() function I am ok with. But then, there is a mention on the check() function:

// string-compare the word entered by the user with words from the dictionary
node* cursor = malloc(sizeof(node));
cursor = hashtables[index_text];

We don't need to malloc a node to check an existing node. So, I changed those three lines to these two:

// string-compare the word entered by the user with words from the dictionary
node* cursor = hashtables[index_text];

Because, we were overwriting the malloced node with the node in hastables[index_text] anyways.

That took one error from valgrind away.

Then, I was pretty clueless about what to do next so I googled it. I found this awesome answer to this awesome student:

pset5 speller.c with hashtable errors and seg fault

Notice at this on Kareem's answer:

"also do you think relying on feof may cause you to allocate more memory than you need?"

At first I did not understand. But looking at the code I realized that we are mallocing without knowing if the fread was successful or if it was the end of the file. So we are always mallocing one last node that does not get freed. It does not get freed because it does not get added to the hashtable.

So I added these lines:

    if(feof(fp_dict)){
        free(new_node);
        break;
    }

After adding that piece you don't even really need a condition in the while loop. The loop could be while(true), since it will always break in this recent piece of code.

Here it is with some context in the load function so you know where to put the block of code. Pretty much right after the fscanf() line:

// perform a while loop whenever it is not the end of the dictionary yet
while(!feof(fp_dict))
{
   // make a new pointer pointing to a new word from the dictionary and scan the word this pointer points to
   node* new_node = malloc(sizeof(node));
   fscanf(fp_dict, "%s", new_node -> word_dict);

    if(feof(fp_dict)){
        free(new_node);
        break;
    }

   // hash the word from the dictionary and obtain the resulting index
   int hash = hash_function(new_node -> word_dict);

This way, you break out of the loop and free your recently created node before you break out of the loop. The way your code works, you need to malloc the node before reading the file, so I think this is a valid solution.

I think that one got rid of 2 valgrind errors somehow.

I ran check50 and valgrind after that with no errors.

6
  • Thank you for all the comments! Now, check50 gives all the happy faces, except that there are still many memory leaks, and in fact, more. This is a program that takes in arguments, so when we valgrind it, we have to include the arguments in the command as well. Instead of valgrind --leak-check=full --show-leak-kinds=all -v ./speller I ran valgrind --leak-check=full --show-leak-kinds=all -v ./speller austen.txt And many memories were leaked. Please help.
    – Alex Chan
    Nov 2 '16 at 5:35
  • You are very welcome. I am sorry for my ignorance with valgrind! I got all the errors you mentioned. I also changed the code and got rid of all three of them. Check my updated answer. Nov 2 '16 at 13:32
  • 1
    Check SECOND UPDATE Nov 2 '16 at 13:32
  • Thank you for helping me Ricardo. I really appreciate your help! I made all the changes per your instructions but memories are still leaking. When you pointed out how each correction should tackle each leak, those corrections did not work on my end. I guess I better show you the latest code I have as well as my valgrind report, for your reference. The code and the valgrind report are too long to be posted here, so I made a new post instead, available here: cs50.stackexchange.com/questions/21669/… Please help me. I am too frustrated. THANK YOU!
    – Alex Chan
    Nov 3 '16 at 6:02
  • It finally worked Ricardo! Thank you for all the efforts again!!!!!!!!
    – Alex Chan
    Nov 5 '16 at 7:22

You must log in to answer this question.

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