unavoidable memory leaks when two nodes points to each other

Question

I am having a very strange problem with shared_ptr where two Node are using shared_ptr to point to each other.

I paste my test code and output valgrind first, then follow my understanding.

test code

#include <iostream>
#include <memory>

struct Node {
  int val_;
  std::shared_ptr<Node> next_;
  std::shared_ptr<Node> prev_;

  Node(int val)
      : val_(val), next_(nullptr), prev_(nullptr) {
  }
};

class List {
public:
  List() 
      : head_(nullptr){
  }

  void insert(int val) {
    auto new_node = std::make_shared<Node>(val);
    if (!head_)
      head_ = new_node;
    else {
      head_->next_ = new_node;
      new_node->prev_ = head_;
    }
  }

  void debug() {
    std::shared_ptr<Node> cur;
    for (cur = head_; cur != nullptr; cur = cur->next_)
      std::cout << cur->val_ << std::endl;
  }
private:
  std::shared_ptr<Node> head_;
};

int main(int argc, const char *argv[]) {
  List l;
  l.insert(199);
  l.insert(200);

  l.debug();

  return 0;
}

the output of valgrind.

==8282== Memcheck, a memory error detector
==8282== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==8282== Using Valgrind-3.9.0 and LibVEX; rerun with -h for copyright info
==8282== Command: ./a.out
==8282== 
==8282== 
==8282== HEAP SUMMARY:
==8282==     in use at exit: 128 bytes in 2 blocks
==8282==   total heap usage: 2 allocs, 0 frees, 128 bytes allocated
==8282== 
==8282== 128 (64 direct, 64 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==8282==    at 0x4C28C90: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8282==    by 0x401825: __gnu_cxx::new_allocator<std::_Sp_counted_ptr_inplace<Node, std::allocator<Node>, (__gnu_cxx::_Lock_policy)2> >::allocate(unsigned long, void const*) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x401751: std::allocator_traits<std::allocator<std::_Sp_counted_ptr_inplace<Node, std::allocator<Node>, (__gnu_cxx::_Lock_policy)2> > >::allocate(std::allocator<std::_Sp_counted_ptr_inplace<Node, std::allocator<Node>, (__gnu_cxx::_Lock_policy)2> >&, unsigned long) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x4015B1: std::__shared_count<(__gnu_cxx::_Lock_policy)2>::__shared_count<Node, std::allocator<Node>, int&>(std::_Sp_make_shared_tag, Node*, std::allocator<Node> const&, int&) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x4014FB: std::__shared_ptr<Node, (__gnu_cxx::_Lock_policy)2>::__shared_ptr<std::allocator<Node>, int&>(std::_Sp_make_shared_tag, std::allocator<Node> const&, int&) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x401451: std::shared_ptr<Node>::shared_ptr<std::allocator<Node>, int&>(std::_Sp_make_shared_tag, std::allocator<Node> const&, int&) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x40139D: std::shared_ptr<Node> std::allocate_shared<Node, std::allocator<Node>, int&>(std::allocator<Node> const&, int&) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x4011D2: _ZSt11make_sharedI4NodeIRiEESt10shared_ptrIT_EDpOT0_ (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x401000: List::insert(int) (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282==    by 0x400DAC: main (in /home/lightmanhk/Backup/repo/scripts_code/docs/c++/tech/module/shared_ptr/a.out)
==8282== 
==8282== LEAK SUMMARY:
==8282==    definitely lost: 64 bytes in 1 blocks
==8282==    indirectly lost: 64 bytes in 1 blocks
==8282==      possibly lost: 0 bytes in 0 blocks
==8282==    still reachable: 0 bytes in 0 blocks
==8282==         suppressed: 0 bytes in 0 blocks
==8282== 
==8282== For counts of detected and suppressed errors, rerun with: -v
==8282== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 1 from 1)

understanding

|------|               |-------|
|next----------------->|next(nullptr)
|prev(nullptr)|<--------prev   |
|------|               |-------|
 head_                  new_node

I believe the reason why I am having the memory leaks is that when List's destructor gets called, it only reduce the reference to head_ by 1 rather than free the head_(because new_node->prev_ points to head_ as well). (maybe I am wrong?)

1> my question how to solve this problem.

Hope someone give me suggestions. thanks a lot.

if you're relying on node destruction for chaining your object destructions on shared-pointer reference counts reaching zero, you may want to consider the ramifications of that, particularly with something, say, 100,000 nodes in the list. Don't forget each node being destroyed will trigger the destructor of the next node, and that can *quickly* eat your call-activation stack space. — WhozCraig, Feb 18 '14 at 07:17

score 2 · Accepted Answer · answered Feb 18 '14 at 07:13

You are correct. There are a lot of ways to fix this problem, but I recommend not allowing circles of strong pointers. One simple fix for this class is to make the forward pointer a strong pointer and the back pointer a weak pointer. That way, deleting the list will delete the only strong pointer to the head node, which will delete the only strong pointer to the second node, and so on.

When manipulating nodes in the list, make sure to hold your own strong pointers to the nodes you are manipulating to make sure they don't get destroyed while you are manipulating their forward pointers.

This isn't really a very good solution. It breaks the orthogonality between the two pointers, and adds extra complexity for nothing. It's much easier here to just forget about `shared_ptr` (which is really only applicable to special cases anyway), and manage the memory directly in the `List` class. — James Kanze, Feb 18 '14 at 09:04

score 2 · Answer 2 · edited May 23 '17 at 10:31

shared_ptr is not a panacea. You should ask yourself if each Node owns the next/previous Node.

An alternative is for List to own all the Nodes, and for the Node to link to other Nodes.

Semantically, shared_ptr and unique_ptr imply ownership, and * (or &) imply a relationship.

For a recent example of a different data structure, see Is there a more efficient implementation for a bidirectional map?. You can see that there's a nice split between managing the memory of the objects and managing the relationships between the objects.

score 0 · Answer 3 · answered Feb 18 '14 at 09:02

You don't give much context, but if these are nodes of a graph, you probably don't want smart pointers at all. In such cases, the best solution is generally to let the graph object take care of all memory management of its nodes, since it (and only it) knows when a node is no longer used. shared_ptr is not a good solution here. (Note that none of the implementations of std::list that I've seen use shared_ptr.)

unavoidable memory leaks when two nodes points to each other

test code

the output of valgrind.

understanding

3 Answers3