Why does Valgrind report memory leaks on Binary Search Tree (BST) still?

Question

void DeleteNodes(BTNode* node)
{
    // Recurse left down the tree...
    if(node->left != NULL)
    {
        DeleteNodes(node->left);
    }
    if(node->right != NULL)
    {
        DeleteNodes(node->right);
    }


    // Free memory used by the node itself.
    delete node;
}

This is what Valgrind yells at me.

==20793== Invalid read of size 8
==20793==    at 0x407B68: toString(std::string, NodeInterface*) (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x4081CF: printBST(BSTInterface*) (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x40856F: printError() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x4028E9: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==  Address 0x4c448b0 is 0 bytes inside a block of size 32 free'd
==20793==    at 0x4A07991: operator delete(void*) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20793==    by 0x407785: BTNode::~BTNode() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x407213: DeleteChildren(BTNode*) (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x4075A7: BST::clear() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x402874: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793== 
pure virtual method called
terminate called without an active exception

I have been debugging this particular bit of code. The program was not reporting these memory leaks before I implemented this piece. I have looked up different Valgrind errors and I understand that Invalid read of size 8 means that it is attempting to access memory that has already been freed (http://valgrind.org/docs/manual/mc-manual.html). However, I can't figure out where the recursive algorithm is accesing the same memory over and over again. I also found a few other answers to this on StackExchange like this:Valgrind... 4 bytes inside a block of size 8 free'd. It doesn't help in my case because I'm not using double pointers to my knowledge. Anyways, if anymore code is needed i can post, but this is the only one that is giving issue thus far. I can also post the rest of the code in this .cpp file but as far as I can tell its irrelevant because there were no memory leak errors until I put in this code.

Here is the memory report after Valgrind has finished running.

==20793== HEAP SUMMARY:
==20793==     in use at exit: 8,953 bytes in 6 blocks
==20793==   total heap usage: 2,036 allocs, 2,030 frees, 811,313 bytes allocated
==20793== 
==20793== 24 bytes in 1 blocks are still reachable in loss record 1 of 6
==20793==    at 0x4A06965: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20793==    by 0x401DC3: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793== 
==20793== 26 bytes in 1 blocks are possibly lost in loss record 2 of 6
==20793==    at 0x4A06965: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20793==    by 0x30020BDCF8: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator<char> const&) (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x30020BF5B0: char* std::string::_S_construct<char const*>(char const*, char const*, std::allocator<char> const&, std::forward_iterator_tag) (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x30020BF9E7: std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&) (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x40819C: printBST(BSTInterface*) (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x40856F: printError() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x4028E9: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793== 
==20793== 32 bytes in 1 blocks are still reachable in loss record 3 of 6
==20793==    at 0x4A06965: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20793==    by 0x407838: Factory::getBST() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x401DDA: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793== 
==20793== 111 bytes in 1 blocks are possibly lost in loss record 4 of 6
==20793==    at 0x4A06965: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20793==    by 0x30020BDCF8: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator<char> const&) (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x30020BE93A: std::string::_Rep::_M_clone(std::allocator<char> const&, unsigned long) (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x30020BE9E3: std::string::reserve(unsigned long) (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x30020BEAA7: std::string::append(std::string const&) (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x408A16: printBeforeError() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x4026F3: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793== 
==20793== 568 bytes in 1 blocks are still reachable in loss record 5 of 6
==20793==    at 0x4A0645D: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20793==    by 0x3FFD46C52C: __fopen_internal (in /usr/lib64/libc-2.18.so)
==20793==    by 0x300207CA1F: std::__basic_file<char>::open(char const*, std::_Ios_Openmode, int) (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x30020B77F9: std::basic_filebuf<char, std::char_traits<char> >::open(char const*, std::_Ios_Openmode) (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x40853A: printError() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x4028E9: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793== 
==20793== 8,192 bytes in 1 blocks are still reachable in loss record 6 of 6
==20793==    at 0x4A0700A: operator new[](unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==20793==    by 0x30020B71CB: std::basic_filebuf<char, std::char_traits<char> >::_M_allocate_internal_buffer() (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x30020B7811: std::basic_filebuf<char, std::char_traits<char> >::open(char const*, std::_Ios_Openmode) (in /usr/lib64/libstdc++.so.6.0.19)
==20793==    by 0x40853A: printError() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793==    by 0x4028E9: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
==20793== 
==20793== LEAK SUMMARY:
==20793==    definitely lost: 0 bytes in 0 blocks
==20793==    indirectly lost: 0 bytes in 0 blocks
==20793==      possibly lost: 137 bytes in 2 blocks
==20793==    still reachable: 8,816 bytes in 4 blocks
==20793==         suppressed: 0 bytes in 0 blocks

Post your whole code. That one snippet has nothing obviously wrong with it, so the errors are almost certainly elsewhere. — Adam Rosenfield, Nov 16 '14 at 03:16
Valgrind is telling you that you're accessing already deleted memory; that is unconditionally a bad idea, even in printing code. One of the leaks is caused by your `printBST()` code. — Jonathan Leffler, Nov 16 '14 at 05:14

Why does Valgrind report memory leaks on Binary Search Tree (BST) still?

0 Answers0