如何在使用shared_ptr时检测循环引用

Question

shared_ptr是Boost库中的引用计数智能指针。

引用计数的问题在于它不能处理循环依赖。我在想如何通过C++来解决这个问题。

请不要提出像“不要创建循环”或“使用weak_ptr”之类的建议。

编辑

我不喜欢那些只是建议使用weak_ptr的答案，因为显然，如果你知道你将创建一个循环，那么你就不会有问题。而且，如果在运行时生成shared_ptr，你也无法在编译时确定是否会有循环。

因此，请自行删除那些包含weak_ptr的答案，因为我特别要求不要提供这种答案...

- Unknown

---

你能否提供一些关于你正在尝试解决的问题的详细信息？（编辑帖子） - Chris Huang-Leaver

你知道吗，听起来你需要一个垃圾回收器。C++有这样的工具。其中一个可以在这里找到：http://www.hpl.hp.com/personal/Hans_Boehm/gc/，但我没有使用过，也无法告诉你它的效果如何。 但是，说真的，请修复你的设计问题。 - Ori Pessach

我不喜欢Boehm保守的垃圾收集器，因为随着堆栈和堆的增长，它会泄漏得很厉害。拥有shared_ptr的循环并不一定意味着设计需要“修复”。否则，Java和.NET将具有引用计数GC。 - Unknown

“拥有 shared_ptr 的周期并不一定意味着该设计需要被“修复”。” 这句话的意思是，即使一个设计中使用了 shared_ptr 对象的周期性所有权管理方式，也不一定就需要对该设计进行修改或改进。 - curiousguy

@curiousguy 他解释说，如果有人正在开发一种编程语言，出现循环是很自然的：编程语言的用户可能会自己创建循环。对于这些情况，拥有垃圾回收器是必要的，而不是糟糕的设计。当然，在许多情况下，GC可能会过度，但是，OP明确表示在他的项目中无法避免循环。 - VinGarcia

Answer 1

shared_ptr 表示 拥有关系，而weak_ptr 则表示 感知关系。当多个对象相互拥有时，这意味着你在架构上存在问题，这可以通过将一个或多个 拥有 变为 感知（即 weak_ptr）来解决。

我不明白为什么建议使用 weak_ptr 被认为是无用的。

- n0rd

---

如果您事先知道只会有一个静态所有者，那么auto_ptr就足够了，您不需要shared_ptr。我一直认为shared_ptr是一种“最后一个离开，关灯”的机制。 - Mark Ransom

拥有一个指向对象的shared_ptr意味着控制该对象的生命周期。 如果使用weak_ptr就足够了，而你仍然使用shared_ptr，那么很可能你在更多的地方控制了对象的生命周期，这是你所能想象到的。 - n0rd

弱指针是一种设计决策，在通常情况下是对使用情况的限制。 - Sam Ginrich

Answer 2

我理解你被轻率地告知使用 weak_ptr 来打破循环引用的方式所困扰，当被告知循环引用是不好的编程风格时，我自己也感到几乎愤怒。

你特别询问如何发现循环引用。事实上，在一个复杂的项目中，一些引用周期是间接的且难以发现的。

答案是你不应该做出虚假声明，让自己容易受到循环引用的攻击。我很严肃，并批评了一种非常流行的做法 - 盲目地在所有情况下使用 shared_ptr。

在设计中应清晰明确哪些指针是所有者，哪些是观察者。

对于所有者，请使用 shared_ptr。

对于观察者，请使用 weak_ptr - 不仅限于那些你认为可能会构成循环引用的部分。

如果你遵循这个惯例，循环引用将不会引起任何问题，你也不需要担心它们。

当你想要使用它们时，当然你需要写很多代码将所有这些 weak_ptr 转换为 shared_ptr - Boost 真的做不到这个工作。

- John Morrison

---

+1 表示“所有的元素，而不仅仅是您认为可能是循环的部分”。 - SAS

Answer 3

检测循环引用相对简单：

• 将计数器设置为某个较大的数字，比如1000（确切大小取决于您的应用程序）
• 从您感兴趣的指针开始，并跟随其指向的指针
• 对于您跟随的每个指针，将计数器减一
• 如果在到达指针链的末尾之前计数器降至零，则存在循环引用

然而，这并不是非常有用。对于引用计数指针，通常无法解决循环问题 - 这就是为什么发明了像代际清除这样的替代垃圾回收方案。

- anon

---

这似乎不是正确的答案。该答案并没有“检测”循环，相反，该算法只是说“代码中可能存在循环”。 - Kartal Tabak

“following”需要比shared_ptr更多的设计。 - Sam Ginrich

Answer 4

我还没有找到比绘制大型UML图并寻找循环更好的方法。

调试时，我使用一个实例计数器进入注册表，像这样：

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
};

我只需要将这些类添加到相应的位置，并查看注册表。

（如果ID被指定为例如“XYZ！”将被转换为字符串。不幸的是，您不能将字符串常量作为模板参数指定）

- peterchen

---

什么是 RegHelper？ - Ashish Negi

Answer 5

也许是 boost::weak_ptr 和 boost::shared_ptr 的组合？ 这篇文章可能会引起您的兴趣。

- dirkgently

Answer 6

我认为你真正想要的是类似于Java垃圾收集的东西。 这个问题讨论了用于shared_ptr的“自动周期破坏器”。

您可以在程序中拥有 shared_ptr 循环并使每个对象去除，但这违反了普遍的建议。普遍的建议是通过在参与循环的对象中使用 weak_ptr 来 打破 shared_ptr 循环。

如果您坚持在程序中保留 shared_ptr 循环，则仍然可以这样做，但是必须在销毁时手动打破 shared_ptr 循环。

这很像记住手动调用 delete 以删除对象，因此不推荐这样做。

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;

}

- bobobobo

---

Java 实现一种异步垃圾回收，这是其中的一个选项。 - Sam Ginrich

@SamGinrich 垃圾回收虽然慢... - Alexis Wilke

是的，我指的是它与操作函数并发运行。您也可以同步进行，即立即识别未使用的对象，这在有实时要求时可能更好。 - Sam Ginrich

Answer 7

如果你的C++程序使用了共享指针，那么可能会出现内存泄漏。如果你想要查找这些内存泄漏对象的类型，可以通过查看它们的类型来找到实际的循环引用。请注意，保留HTML标签。

- Ashish Negi

Answer 8

请查看关于检测图中环路的帖子。

- Mr Fooz

Answer 9

寻找循环的通用解决方案可以在此处找到：

最佳算法测试链表是否有循环

这假设您知道列表中对象的结构，并且可以跟随每个对象中包含的所有指针。

- Mark Ransom

---

我想知道人们在使用shared_ptr时具体如何做到这一点。在我看来，您需要添加一些开销，将所有shared_ptrs转换为有向图，并跟踪它们的所有者。我想知道通常处理此问题的方法。 - Unknown

Shared_ptr并不保留图表，只保留未解除的有效指针数量。这就是为什么你不能遍历它以查找循环，除非你知道指针的使用方式。 - Mark Ransom

@ Mark，我的观点是你需要创建一个shared_ptr的有向图来收集循环。 - Unknown

不一定，如果您有能力检索每个类的“反射”数据，那么您可以简单地从一个类开始，将其标记为已标记，然后移动到类中包含的每个指针，随着您的移动标记每个指针，然后在离开递归函数时取消标记。如果您遇到已经标记的类，则找到了一个循环。 - Grant Peters

Answer 10

您可能需要一种垃圾回收技术，例如标记清除法。该算法的思想是：

1. 维护一个指向所有已分配内存块的引用列表。
2. 在某个时刻启动垃圾回收器：
   1. 首先标记所有仍然可以访问的块，而无需使用引用列表。
   2. 遍历列表，删除每个未被标记的项，这意味着它不再可达，因此没有用处。

由于您正在使用shared_ptr，任何您未能到达的现有指针都应视为循环的成员。

实现

下面我描述了如何实现算法的sweep()部分的非常简单的示例，但它将重置收集器上的所有剩余指针。

此代码存储shared_ptr<Cycle_t>指针。类Collector负责跟踪所有指针，并在执行sweep()时删除它们。

#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.
    }
  }
};

你可以像这样使用它：

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();
  }
}

我使用了Valgrind进行了测试，没有列出任何内存泄漏或“仍可访问”块，所以它可能按预期工作。

关于此实现的一些注意事项：

1. 内存向量将无限增长，您应该使用某些内存分配技术来确保它不会占用所有工作内存。
2. 有人可能会认为，在实现这样的垃圾收集器时，没有必要使用类似引用计数GC的shared_ptr，因为标记和清除算法已经可以处理这个任务。
3. 我没有实现mark()函数，因为它会使示例变得复杂，但是这是可能的，我将在下面解释。

最后，如果您担心（2），这种实现方式并不罕见。CPython（Python的主要实现）确实使用了引用计数和标记-清除的混合，但主要是出于历史原因。

实现mark()函数：

为了实现mark()函数，您需要进行一些修改：

需要在Cycle_t中添加一个bool marked;属性，并使用它来检查指针是否已标记。

您需要编写Collector::mark()函数，其代码如下：

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

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

然后您需要修改sweep()函数，如果指针已被标记，则删除该标记，否则reset()指针：

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();
      }
    }
  }
}

这是一篇详细的说明，希望能对某些人有所帮助。

- VinGarcia