Implementing a trie. Updated load function in dictionary.c causes more problems with valgrind

Question

I've been trying to fix an error that valgrind indicated came from my load() function. So in the beginning I implemented load() like this: http://pastebin.com/57a2HPMg Doing so only produced 1 error with valgrind:

==1190== HEAP SUMMARY:
==1190== in use at exit: 3,865,688 bytes in 17,256 blocks
==1190== total heap usage: 367,084 allocs, 349,828 frees, 82,227,504 bytes allocated
==1190==
==1190== 568 bytes in 1 blocks are still reachable in loss record 1 of 4
==1190== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1190== by 0x4EA544C: __fopen_internal (iofopen.c:73)
==1190== by 0x40120E: load (dictionary.c:98)
==1190== by 0x40087D: main (speller.c:45)
==1190==
==1190== 2,464 bytes in 11 blocks are indirectly lost in loss record 2 of 4
==1190== at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1190== by 0x40135D: load (dictionary.c:127)
==1190== by 0x40087D: main (speller.c:45)
==1190==
==1190== 1,948,352 bytes in 8,698 blocks are indirectly lost in loss record 3 of 4
==1190== at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1190== by 0x4012D8: load (dictionary.c:113)
==1190== by 0x40087D: main (speller.c:45)
==1190==
==1190== 3,865,120 (1,914,304 direct, 1,950,816 indirect) bytes in 8,546 blocks are definitely lost in loss record 4 of 4
==1190== at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1190== by 0x40135D: load (dictionary.c:127)
==1190== by 0x40087D: main (speller.c:45)
==1190==
==1190== LEAK SUMMARY:
==1190== definitely lost: 1,914,304 bytes in 8,546 blocks
==1190== indirectly lost: 1,950,816 bytes in 8,709 blocks
==1190== possibly lost: 0 bytes in 0 blocks
==1190== still reachable: 568 bytes in 1 blocks
==1190== suppressed: 0 bytes in 0 blocks
==1190==
==1190== For counts of detected and suppressed errors, rerun with: -v
==1190== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

But then I realised that after going down one node for every char read from the dictionary I couldn't set is_word to true because I would be one node below. So I rewrote load() after relooking at Zamyla's short : http://pastebin.com/WA2n82zV

==1416== Conditional jump or move depends on uninitialised value(s)
==1416== at 0x4012DD: load (dictionary.c:113)
==1416== by 0x4008BD: main (speller.c:45)
==1416== Uninitialised value was created by a stack allocation
==1416== at 0x401230: load (dictionary.c:97)
==1416==
==1416== Use of uninitialised value of size 8
==1416== at 0x4012F7: load (dictionary.c:115)
==1416== by 0x4008BD: main (speller.c:45)
==1416== Uninitialised value was created by a stack allocation
==1416== at 0x401230: load (dictionary.c:97)
==1416==
==1416== Conditional jump or move depends on uninitialised value(s)
==1416== at 0x4013B7: load (dictionary.c:134)
==1416== by 0x4008BD: main (speller.c:45)
==1416== Uninitialised value was created by a stack allocation
==1416== at 0x401230: load (dictionary.c:97)
==1416==
==1416== Use of uninitialised value of size 8
==1416== at 0x40131C: load (dictionary.c:117)
==1416== by 0x4008BD: main (speller.c:45)
==1416== Uninitialised value was created by a stack allocation
==1416== at 0x401230: load (dictionary.c:97)
==1416==
==1416== Use of uninitialised value of size 8
==1416== at 0x40134E: load (dictionary.c:119)
==1416== by 0x4008BD: main (speller.c:45)
==1416== Uninitialised value was created by a stack allocation
==1416== at 0x401230: load (dictionary.c:97)
==1416==
==1416== Use of uninitialised value of size 8
==1416== at 0x401363: load (dictionary.c:120)
==1416== by 0x4008BD: main (speller.c:45)
==1416== Uninitialised value was created by a stack allocation
==1416== at 0x401230: load (dictionary.c:97)
==1416==
==1416== HEAP SUMMARY:
==1416== in use at exit: 322,376,216 bytes in 1,439,178 blocks
==1416== total heap usage: 1,439,233 allocs, 55 frees, 322,388,880 bytes allocated
==1416==
==1416== 568 bytes in 1 blocks are still reachable in loss record 1 of 6
==1416== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1416== by 0x4EA544C: __fopen_internal (iofopen.c:73)
==1416== by 0x40124E: load (dictionary.c:98)
==1416== by 0x4008BD: main (speller.c:45)
==1416==
==1416== 138,880 bytes in 620 blocks are indirectly lost in loss record 2 of 6
==1416== at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1416== by 0x4013E4: load (dictionary.c:138)
==1416== by 0x4008BD: main (speller.c:45)
==1416==
==1416== 1,792,224 bytes in 8,001 blocks are possibly lost in loss record 3 of 6
==1416== at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1416== by 0x4013E4: load (dictionary.c:138)
==1416== by 0x4008BD: main (speller.c:45)
==1416==
==1416== 18,953,088 bytes in 84,612 blocks are indirectly lost in loss record 4 of 6
==1416== at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1416== by 0x40133D: load (dictionary.c:119)
==1416== by 0x4008BD: main (speller.c:45)
==1416==
==1416== 19,092,192 (224 direct, 19,091,968 indirect) bytes in 1 blocks are definitely lost in loss record 5 of 6
==1416== at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1416== by 0x4013E4: load (dictionary.c:138)
==1416== by 0x4008BD: main (speller.c:45)
==1416==
==1416== 301,491,232 bytes in 1,345,943 blocks are possibly lost in loss record 6 of 6
==1416== at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1416== by 0x40133D: load (dictionary.c:119)
==1416== by 0x4008BD: main (speller.c:45)
==1416==
==1416== LEAK SUMMARY:
==1416== definitely lost: 224 bytes in 1 blocks
==1416== indirectly lost: 19,091,968 bytes in 85,232 blocks
==1416== possibly lost: 303,283,456 bytes in 1,353,944 blocks
==1416== still reachable: 568 bytes in 1 blocks
==1416== suppressed: 0 bytes in 0 blocks
==1416==
==1416== For counts of detected and suppressed errors, rerun with: -v
==1416== ERROR SUMMARY: 41 errors from 9 contexts (suppressed: 0 from 0)

Could anyone point out what I'm missing/doing wrongly?

Any advice would be greatly appreciated!

Answer 1

I'm trying to figure out the best way to tell you this so that you can find it on your own, without just telling you where the problems lie. The good news is that the total memory leak code fix is about 15 keystrokes, give or take. Besides, what fun would it be if someone just gave you the answer? ;-)

First, remember that, among other things, valgrind tells you where the lost memory originates, not necessarily where the bug is. In this case, running the command valgrind --leak-check=full ./speller small told me that the line ptr->children[26] = calloc(1, sizeof(node)); is creating the memory that is lost. Think about that. The code you just added (remember your last question?) to handle the apostrophes is generating the memory that is being lost.

Did you remember to think about that and what else needs to be changed? Maybe that new memory isn't being freed somewhere?????? Now where does all the memory get freed? Hmmmm...... ;-)

Now, after you fix that, there's a more specific valgrind command. valgrind --leak-check=full --show-leak-kinds=all ./speller small will point at another line of code that is allocating memory. (You can get these commands by reading the output of the basic valgrind command. It suggests parameters that give more detail.) When you look at that line, ask yourself if there's something you forgot to do later on in load() before exiting? This the smallest memory leak that you have and should have a simple open and shut resolution. ;-D

I'll give you two other observations. Your first version of load(), above, is fine, except for that last problem. Check(), on the other hand, isn't working at all, at least when I ran it, but that's an entirely different question. I didn't look at the second version that you linked to, because of what I found in the first one.

If you really can't find the problem, leave a comment with where you are and I'll point you in the right direction. Anyways, I hope you enjoy finding the solution.

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