CODEWITHSUNDEEP
c++memory-leakslinked-list
scalen121
scalen121

Reputation: 925

Valgrind reporting memory leaks in many places that change between runs

I am creating a linked list but I keep getting memory leaks. Sometimes it says the problem is in the at() function and sometimes in the remove() function, but it all looks pretty tight to me. What is causing memory leaks?

Here is my code for the linked list:

void LinkedList::insertHead(int value)
{
    if (value < 0) {
        return;
    }
    iterator pos(this, head);
    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == value)
            return;
        else
            pos++;
    }
    head = new Node(value, NULL, head);
    if (head->next != NULL)
        head->next->prev = head;
    if (tail == NULL)
        tail = head;
    num_items++;
}

void LinkedList::insertTail(int value)
{
    if (value < 0) {
        return;
    }
    iterator pos(this, head);
    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == value)
            return;
        else
            pos++;
    }
    if (tail != NULL) {
        tail->next = new Node(value, tail, NULL);
        tail = tail->next;
        num_items++;
    } else
        insertHead(value);
}

void LinkedList::insertAfter(int value, int insertionNode)
{
    if (value < 0) {
        return;
    }
    iterator pos(this, head);
    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == value)
            return;
        else
            pos++;
    }
    pos = iterator(this, head);
    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == insertionNode)
            break;
        else
            pos++;
    }
    if (pos.current == NULL || pos.current->data != insertionNode) {
        return;
    } /*else if(pos.current==NULL)
        insertTail(value);*/
    else {
        Node *new_node = new Node(value, pos.current, pos.current->next);
        if (pos.current->next != NULL)
            pos.current->next->prev = new_node;
        pos.current->next = new_node;
        num_items++;
    }

}

void LinkedList::remove(int value)
{
    if (value < 0) {
        return;
    }
    iterator pos(this, head);
    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == value)
            break;
        else
            pos++;
    }
    if (pos.current->data != value) {
        return;
    }
    if (pos.current == head) {
        Node *removed_node = head;
        head = head->next;
        delete removed_node;
        if (head != NULL)
            head->prev = NULL;
        else
            tail = NULL;
        num_items--;
    } else if (pos.current == tail) {
        Node *removed_node = tail;
        tail = tail->prev;
        delete removed_node;
        if (tail != NULL)
            tail->next = NULL;
        else
            head = NULL;
        num_items--;
    } else {
        Node *removed_node = pos.current;
        removed_node->prev->next = removed_node->next;
        removed_node->next->prev = removed_node->prev;
        delete removed_node;
        num_items--;
    }
}

void LinkedList::clear()
{
    if (num_items == 0)
        return;
    if (head != NULL)
        remove(head->data);
    num_items = 0;
}

int LinkedList::at(int index)
{
    if (index < 0 || index >= num_items)
        return -1;
    iterator pos(this, head);
    for (int i = 0; i < index; i++)
        pos++;
    return pos.current->data;
}

int LinkedList::size()
{
    return num_items;
}

Here is code for the iterator:

class iterator {
    friend class LinkedList;
private:
    LinkedList * parent;
    Node *current;
    iterator(LinkedList * my_parent, Node * position):parent(my_parent),
        current(position) {
    }
public:
    int &operator*() const {
        if (current == NULL)
            throw "Attempt to dereference end()";
        return current->data;
    }

    int *operator->() const {
        if (current == NULL)
            throw "attempt to dereference end()";
        return &(current->data);
    }

    iterator & operator++() {
        if (current == NULL)
            throw "Attempt to advance past end()";
        current = current->next;
        return *this;
    }

    iterator & operator--() {
        if (current == parent->head)
            throw "Attempt to move before begin()";
        if (current == NULL)
            current = parent->tail;
        else
            current = current->prev;
        return *this;
    }

    iterator operator++(int) {
        iterator return_value = *this;
        ++(*this);
        return return_value;
    }

    iterator operator--(int) {
        iterator return_value = *this;
        --(*this);
        return return_value;
    }

    bool operator==(const iterator & other) {
        return current == other.current;
    }

    bool operator!=(const iterator & other) {
        return !operator==(other);
    }
};

output as requested:

==18072== Invalid read of size 4
==18072==    at 0x402556: LinkedList::remove(int) (LinkedList.cpp:115)
==18072==    by 0x405946: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==18072== 
segmentation fault
This segmentation fault was most likely caused by insertHead(), insertTail(), insertAfter(), or remove()
==18072== 
==18072== HEAP SUMMARY:
==18072==     in use at exit: 4,074 bytes in 118 blocks
==18072==   total heap usage: 981 allocs, 863 frees, 158,945 bytes allocated
==18072== 
==18072== 16 bytes in 1 blocks are still reachable in loss record 1 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x405888: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 32 bytes in 1 blocks are still reachable in loss record 2 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4020B2: Factory::getLinkedList() (Factory.cpp:21)
==18072==    by 0x40587B: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 32 bytes in 2 blocks are still reachable in loss record 3 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x407AC5: TADuck::insertHead(int) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x405D91: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 48 bytes in 2 blocks are still reachable in loss record 4 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x405D84: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 48 bytes in 2 blocks are indirectly lost in loss record 5 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x40247A: LinkedList::insertAfter(int, int) (LinkedList.cpp:88)
==18072==    by 0x405137: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 192 bytes in 8 blocks are indirectly lost in loss record 6 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x402308: LinkedList::insertTail(int) (LinkedList.cpp:47)
==18072==    by 0x404D9F: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 216 bytes in 9 blocks are indirectly lost in loss record 7 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x404341: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 216 bytes in 9 blocks are indirectly lost in loss record 8 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x404BAD: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 240 bytes in 10 blocks are indirectly lost in loss record 9 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x402308: LinkedList::insertTail(int) (LinkedList.cpp:47)
==18072==    by 0x4046B1: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 240 bytes in 10 blocks are indirectly lost in loss record 10 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x40247A: LinkedList::insertAfter(int, int) (LinkedList.cpp:88)
==18072==    by 0x404897: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 256 bytes in 1 blocks are still reachable in loss record 11 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4074AD: std::vector<int, std::allocator<int> >::_M_insert_aux(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x402B7C: fillMasterList(std::vector<int, std::allocator<int> >&, int) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x404B82: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 432 bytes in 18 blocks are indirectly lost in loss record 12 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x402BFD: initList(LinkedListInterface*, LinkedListInterface*) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x403F78: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 456 bytes in 19 blocks are indirectly lost in loss record 13 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x4039E9: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 480 bytes in 20 blocks are indirectly lost in loss record 14 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x402BFD: initList(LinkedListInterface*, LinkedListInterface*) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x4040DF: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 480 (24 direct, 456 indirect) bytes in 1 blocks are definitely lost in loss record 15 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x4039E9: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 480 (24 direct, 456 indirect) bytes in 1 blocks are definitely lost in loss record 16 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x402374: LinkedList::insertTail(int) (LinkedList.cpp:52)
==18072==    by 0x404D9F: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 537 bytes in 1 blocks are possibly lost in loss record 17 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x38C88B9F48: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator<char> const&) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88BAB1A: std::string::_Rep::_M_clone(std::allocator<char> const&, unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88BABB3: std::string::reserve(unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C8898F75: std::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >::overflow(int) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C889D195: std::basic_streambuf<char, std::char_traits<char> >::xsputn(char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88949A4: std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x4036B6: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 537 bytes in 1 blocks are possibly lost in loss record 18 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x38C88B9F48: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator<char> const&) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88BAB1A: std::string::_Rep::_M_clone(std::allocator<char> const&, unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88BABB3: std::string::reserve(unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C8898F75: std::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >::overflow(int) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C889D195: std::basic_streambuf<char, std::char_traits<char> >::xsputn(char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88949A4: std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x403A7C: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 720 (24 direct, 696 indirect) bytes in 1 blocks are definitely lost in loss record 19 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x404341: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 936 (24 direct, 912 indirect) bytes in 1 blocks are definitely lost in loss record 20 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x402BFD: initList(LinkedListInterface*, LinkedListInterface*) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x403F78: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== LEAK SUMMARY:
==18072==    definitely lost: 96 bytes in 4 blocks
==18072==    indirectly lost: 2,520 bytes in 105 blocks
==18072==      possibly lost: 1,074 bytes in 2 blocks
==18072==    still reachable: 384 bytes in 7 blocks
==18072==         suppressed: 0 bytes in 0 blocks
==18072== 
==18072== For counts of detected and suppressed errors, rerun with: -v
==18072== ERROR SUMMARY: 7 errors from 7 contexts (suppressed: 2 from 2)

Upvotes: 0

Views: 1943

Answers (2)

jxh
jxh

Reputation: 70472

Your valgrind output is reporting memory leaks. However, those can be ignored for now because your program suffered a segmentation fault as a result of an invalid read on memory location 0x0:

==18072== Invalid read of size 4
==18072==    at 0x402556: LinkedList::remove(int) (LinkedList.cpp:115)
==18072==    by 0x405946: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

segmentation fault

You need to find where line 115 is and figure out why the code is trying to deference an invalid memory location. As an example, I will illustrate with the first one I found (I don't know if this is the one that valgrind is complaining about or not, since I do not know what the line numbers are for your code):

    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == value)
            break;
        else
            pos++;
    }
    if (pos.current->data != value) {
        return;
    }

In the case that there is no match for value, it seems unlikely that pos.current will point to a meaningful entry. So dereferencing it to check if it doesn't match for the early return is probably the wrong thing to do. Instead, check if the for loop actually made it through the entire list:

    int i;
    for (i = 0; i < num_items; i++) {
        //...
    }
    if (i == num_items) {
        return;
    }

As you encounter the errors reported in valgrind, address the segmentation faults first, then the Invalid reads or Invalid writes, then the memory leaks.

From your comment, you seemed a little stumped on the process of debugging. This question was about memory leaks, but that turned out to be a symptom of a crash. Hopefully, this answer has helped you to understand a bit better how to understand the output that valgrind reports, but you should spend some time going over its documentation so that you are able to extract the maximum amount of information from it that you can. To that end, your issue has been addressed. However, let me expand this answer slightly to discuss a little bit about debugging.

Debugging is simply a problem solving exercise, and being good at it is a skill. It is a process that can be likened to solving a crime or a mystery, so debugging is when a programmer gets to be the detective. As with most human endeavors, there are people who are much better at debugging than others. But anyone can become a skillful debugger, because it is also true that you can become better a debugging with practice.

I studied a lot of math during high school and college, so I am biased in the belief that debugging is very similar to solving a mathematical problem. With time, you gain an intuition as to how to drive yourself to the solution more quickly, but at a high level, the process I take largely follows the steps laid out by George Polya in his book How to Solve It.

  1. First: Understand the problem. What is the input? What is the output? What output is the program expected to produce? What assumptions and preconditions are required by your program? Have all those conditions been satisfied?

  2. Second: Devise a plan. Is the problem new or is it similar to a problem you have faced in the past? Is there a relationship between the aberrant result and a particular part of your program? What assumptions and preconditions are required by that part of your program for it to behave correctly? Are you able to test those conditions?

  3. Third: Carry out the plan. If the problem is not new, resolve the issue by applying a fix similar to what you had done before if possible. Otherwise, inspect the state of the program step by step to make sure all the assumptions and preconditions are being satisfied. Determine at what point the program behavior deviate from what it should have done. At the point of deviation, understand the cause of the deviation, and take the appropriate corrective action.

  4. Fourth: Looking back. After the program has been corrected, take the steps needed to convince yourself that the fix is correct. Whatever tests that had passed in the past should still pass. Whatever test had caused the failure should now pass. Identify new tests that may expose other weaknesses in that part of the code. Understand why the problem was introduced, and think of ways that you can change how you write programs in the future that will either make it less likely to make the same error, or make the cause of the problem easier to identify.

Upvotes: 1

Roberto
Roberto

Reputation: 3083

In this code segment from remove,

iterator pos(this, head);
for (int i = 0; i < num_items; i++) {
    if (pos.current->data == value)
        break;
    else
        pos++;
}
if (pos.current->data != value) {
    return;
}

you advance pos to the very end of your list (if value is not found, at least), so might pos.current be NULL when you try to access pos.current->data afterwards?

Upvotes: 1

Related Questions