How to detect cycles when using shared_ptr

Question

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 a 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 in compile time if you generate shared_ptrs during runtime.

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

Answer 1

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)

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

See this post on detecting cycles in a graph.

Answer 7

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.

Answer 8

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.

Answer 9

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 ***

Answer 10

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.