CODEWITHSUNDEEP
c++garbage-collectionshared-ptrreference-counting
Unknown
Unknown

Reputation: 46811

How to detect cycles when using shared_ptr

shared_ptr is a reference counting smart pointer in the Boost library.

The problem with reference counting is that it cannot dispose of cycles. I am wondering how one would go about solving this in C++.

Please no suggestions like: "don't make cycles", or "use weak_ptr".

Edit

I don't like suggestions that say to just use a weak_ptr because obviously if you know you will create a cycle, then you wouldn't have a problem. You also cannot know you will have a cycle at compile time if you generate shared_ptrs at runtime.

So please, self delete answers that use weak_ptr in them because I specifically asked not to have those kind of answers...

Upvotes: 26

Views: 10341

Answers (13)

Satyaanveshi
Satyaanveshi

Reputation: 169

How about just using Valgrind or LLVM's address santizer?

For something like:

#include <bits/stdc++.h>
using namespace std;

struct A {
shared_ptr<A> p;
    ~A() { cout << "Destructor called" << endl; }
};

int main() {
  shared_ptr<A> x(new A);
  shared_ptr<A> y(new A);
  x -> p = y;
  y -> p = x;
  return 0;
}

I see:

==12156== Memcheck, a memory error detector
==12156== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==12156== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info
==12156== Command: ./a.out
==12156==
==12156==
==12156== HEAP SUMMARY:
==12156==     in use at exit: 80 bytes in 4 blocks
==12156==   total heap usage: 5 allocs, 1 frees, 72,784 bytes allocated
==12156==
==12156== 80 (16 direct, 64 indirect) bytes in 1 blocks are definitely lost in loss record 4 of 4
==12156==    at 0x4844F2F: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12156==    by 0x40121C: main (main.cpp:37)
==12156==
==12156== LEAK SUMMARY:
==12156==    definitely lost: 16 bytes in 1 blocks
==12156==    indirectly lost: 64 bytes in 3 blocks
==12156==      possibly lost: 0 bytes in 0 blocks
==12156==    still reachable: 0 bytes in 0 blocks
==12156==         suppressed: 0 bytes in 0 blocks
==12156==
==12156== For lists of detected and suppressed errors, rerun with: -s
==12156== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

The definitely lost: 16 bytes in 1 blocks detects it. You can get a similar output with the address sanitizer. I agree that Valgrind / ASan will detect other stuff too and will not pin-point the cause, but it will detect the circular dependency.

Upvotes: 0

bobobobo
bobobobo

Reputation: 67286

I think you're really asking for something like Java's garbage collection. This question talks about an "automatic cycle breaker" for shared_ptr.

You can have shared_ptr cycles in your program and have every object deallocate, but it's against the popular recommendation. The popular recommendation is to break the shared_ptr cycle by using weak_ptr in one of the objects that participates in the cycle.

If you insist on keeping a shared_ptr cycle in your program, you still can do it, but you have to manually break the shared_ptr cycle at destruction time.

This is a lot like remembering to manually call delete on an object, so you can see why it's not recommended.

struct B;

struct A {
    shared_ptr<B> b;
    void prepForShutdown() {
        b = nullptr; // unlink from b.
    }
    ~A() { puts("~A"); }
};

struct B {
    shared_ptr<A> a;
    ~B() { puts("~B"); }
};

int main() {
    shared_ptr<A> a = make_shared<A>();
    shared_ptr<B> b = make_shared<B>();
    a->b = b;
    b->a = a;

    a->prepForShutdown();  // Break the cycle
    // Without this, either dtor cannot run, because A holds a reference 
    // to b and B holds a reference to A.

    a = nullptr;
    b = nullptr;

}

Upvotes: 1

Ashish Negi
Ashish Negi

Reputation: 5301

If you have Cycles with shared pointers, you will have memory leak. So, if you dump memory leak objects, you can look at the types of these to find the actual cycle.

Upvotes: 1

John Morrison
John Morrison

Reputation: 517

I understand your annoyance at being glibly told to use weak_ptr to break cyclic references and myself I almost feel rage when I am told that cyclic references are bad programming style.

Your ask specifically how do you spot cyclic references. The truth is that in a complex project some reference cycles are indirect and difficult to spot.

The answer is that you should not make false declarations that leave you vulnerable to cyclic references. I am serious and I am criticizing a very popular practice - blindly using shared_ptr for everything.

You should be clear in your design which pointers are owners and which are observers.

For owners use shared_ptr.

For observers use weak_ptr - all of them, not just those you think may be part of a cycle.

If you follow this practice then the cyclic references will not cause any problems and you don't need to worry about them. Of course you will have a lot of code to write to convert all these weak_ptrs to shared_ptrs when you want to use them - Boost really isn't up to the job.

Upvotes: 23

VinGarcia
VinGarcia

Reputation: 1205

You are probably in need of a Garbage Collector technique such as Mark and Sweep. The idea of this algorithm is:

  1. Keep a list with references to all memory blocks allocated.
  2. At some point you start the garbage collector:
    1. It first marks all the blocks it can still access without using the reference list.
    2. It goes through the list erasing each item that could not be marked, implying it is not reachable anymore so it is not useful.

Since you are using shared_ptr any still existing pointers you fail to reach should be considered as members of a cycle.

Implementation

Below I describe a very naive example of how to implement the sweep() part of the algorithm, but it will reset() all remaining pointers on the collector.

This code stores shared_ptr<Cycle_t> pointers. The class Collector is responsible for keeping track of all the pointers and deleting them when sweep() is executed.

#include <vector>
#include <memory>

class Cycle_t;
typedef std::shared_ptr<Cycle_t> Ref_t;

// struct Cycle;
struct Cycle_t {
  Ref_t cycle;

  Cycle_t() {}
  Cycle_t(Ref_t cycle) : cycle(cycle) {}
};

struct collector {
  // Note this vector will grow endlessy.
  // You should find a way to reuse old links
  std::vector<std::weak_ptr<Cycle_t>> memory;

  // Allocate a shared pointer keeping
  // a weak ref on the memory vector:
  inline Ref_t add(Ref_t ref) {
    memory.emplace_back(ref);
    return ref;
  }
  inline Ref_t add(Cycle_t value) {
    Ref_t ref = std::make_shared<Cycle_t>(value);
    return add(ref);
  }
  inline Ref_t add() {
    Ref_t ref = std::make_shared<Cycle_t>();
    return add(ref);
  }

  void sweep() {
    // Run a sweep algorithm:
    for (auto& ref : memory) {
      // If the original shared_ptr still exists:
      if (auto ptr = ref.lock()) {
        // Reset each pointer contained within it:
        ptr->cycle.reset();

        // Doing this will trigger a deallocation cascade, since
        // the pointer it used to reference will now lose its
        // last reference and be deleted by the reference counting
        // system.
        //
        // The `ptr` pointer will not be deletd on the cascade
        // because we still have at least the current reference
        // to it.
      }
      // When we leave the loop `ptr` loses its last reference
      // and should be deleted.
    }
  }
};

You can then use it like this:

Collector collector;

int main() {
  // Build your shared pointers:
  {
    // Allocate them using the collector:
    Ref_t c1 = collector.add();
    Ref_t c2 = collector.add(c1);

    // Then create the cycle:
    c1.get()->cycle = c2;

    // A normal block with no cycles:
    Ref_t c3 = collector.add();
  }

  // In another scope:
  {
    // Note: if you run sweep an you still have an existing
    // reference to one of the pointers in the collector
    // you will lose it since it will be reset().
    collector.sweep();
  }
}

I tested it with Valgrind and no memory leaks or "still reachable" blocks were listed, so it is probably working as expected.

Some notes on this implementation:

  1. The memory vector will grow endlessly, you should use some memory allocation technique to make sure it does not occupy all your working memory.
  2. One may argue that there is no need of using shared_ptr (that works like a Reference Counting GC) to implement such a Garbage Collector since the Mark and Sweep algorithm would already take care of the job.
  3. I did not implement the mark() function because it would complicate the example but it is possible and I will explain it below.

Finally, if you are concerned with (2), this kind of implementation is not unheard of. CPython (the main implementation of Python) does use a mixture of Reference Counting and Mark and Sweep, but mostly for historical reasons.

Implementing the mark() function:

To implement the mark() function you will need to make some modifications:

It would be required to add a bool marked; attribute to Cycle_t, and use it to check whether the pointer is marked or not.

You will need to write the Collector::mark() function that would look like this:

void mark(Ref_t root) {
  root->marked = true;

  // For each other Ref_t stored on root:
  for (Ref_t& item : root) {
    mark(item);
  }
}

And then you should modify the sweep() function to remove the mark if the pointer is marked or else reset() the pointer:

void sweep() {
  // Run a sweep algorithm:
  for (auto& ref : memory) {
    // If it still exists:
    if (auto ptr = ref.lock()) {
      // And is marked:
      if (ptr->marked) {
        ptr->marked = false;
      } else {
        ptr->cycle.reset();
      }
    }
  }
}

It was a lengthy explanation, but I hope it helps someone.

Upvotes: 1

Jame Leung
Jame Leung

Reputation: 1

Answer for the old question, you may try out the intrusive pointer which may help out to count how many times the resource being referred.

#include <cstdlib>
#include <iostream>

#include <boost/intrusive_ptr.hpp>

class some_resource
{
    size_t m_counter;

public:
    some_resource(void) :
        m_counter(0)
    {
        std::cout << "Resource created" << std::endl;
    }

    ~some_resource(void)
    {
        std::cout << "Resource destroyed" << std::endl;
    }

    size_t refcnt(void)
    {
        return m_counter;
    }

    void ref(void)
    {
        m_counter++;
    }

    void unref(void)
    {
        m_counter--;
    }
};

void
intrusive_ptr_add_ref(some_resource* r)
{
    r->ref();
    std::cout << "Resource referenced: " << r->refcnt()
              << std::endl;
}

void
intrusive_ptr_release(some_resource* r)
{
    r->unref();
    std::cout << "Resource unreferenced: " << r->refcnt()
              << std::endl;
    if (r->refcnt() == 0)
        delete r;
}

int main(void)
{
    boost::intrusive_ptr<some_resource> r(new some_resource);
    boost::intrusive_ptr<some_resource> r2(r);

    std::cout << "Program exiting" << std::endl;

    return EXIT_SUCCESS;
}

Here's the result returned.

Resource created 
Resource referenced: 1 
Resource referenced: 2 
Program exiting 
Resource unreferenced: 1
Resource unreferenced: 0 
Resource destroyed
*** Program Exit ***

Upvotes: 0

Mark Ransom
Mark Ransom

Reputation: 308432

The generic solution to finding a cycle can be found here:

Best algorithm to test if a linked list has a cycle

This assumes that you know the structure of the objects in the list, and can follow all of the pointers contained in each object.

Upvotes: 1

n0rd
n0rd

Reputation: 12670

shared_ptr represents ownership relation. While weak_ptr represents awareness. Having several objects owning each other means you have problems with architecture, which is solved by changing one or more own's into aware of's (that is, weak_ptr's).

I don't get why suggesting weak_ptr is considered useless.

Upvotes: 28

Mr Fooz
Mr Fooz

Reputation: 111956

See this post on detecting cycles in a graph.

Upvotes: 1

MighMoS
MighMoS

Reputation: 1254

I know you said "no weak_ptr" but why not? Having your head with a weak_ptr to tail, and tail with a weak_ptr to head will prevent the cycle.

Upvotes: -1

dirkgently
dirkgently

Reputation: 111210

A combination of boost::weak_ptr and boost::shared_ptr maybe? This article may be of interest.

Upvotes: 3

peterchen
peterchen

Reputation: 41116

I haven't found a much better method than drawing large UML graphs and looking out for cycles.

To debug, I use an instance counter going to the registry, like this: 

template <DWORD id>
class CDbgInstCount
{
public:
#ifdef _DEBUG
   CDbgInstCount()   { reghelper.Add(id, 1); }
   CDbgInstCount(CDbgInstCount const &) {  reghelper.Add(id, 1); }
   ~CDbgInstCount()  { reghelper.Add(id, -1); }
#else
#endif
};

I just ned to add that to the classes in question, and have a look at the registry.

(The ID, if given as e.g. 'XYZ!' will be converted to a string. Unfortunately, you can't specify a string constant as template parameter)

Upvotes: 4

anon
anon

Reputation:

It's fairly easy to detect cycles:

  • set a count to some largish number, say 1000 (exact size depends on your application)
  • start with the pionter you are interested in and follow pointers from it
  • for each pointer you follow, decrement the count
  • if the count drops to zero before you reach the end of the pointer chain, you have a cycle

It's not, however, very useful. And it is not generally possible to solve the cycvle problem for ref-counted pointers - that's why alternative garbage colection schemes like generation scavenging were invented.

Upvotes: 4

Related Questions