Как обнаружить циклы при использовании shared_ptr

https://stackoverflow.com/questions/776042

13-09-2019
|

Вопрос

shared_ptr - это интеллектуальный указатель для подсчета ссылок в библиотеке Boost.

Проблема с подсчетом ссылок заключается в том, что он не может удалять циклы.Мне интересно, как можно было бы решить эту проблему на C ++.

Пожалуйста, никаких предложений вроде:"не создавайте циклов" или "используйте weak_ptr".

Редактировать

Мне не нравятся предложения, в которых говорится просто использовать weak_ptr, потому что, очевидно, если вы знаете, что создадите цикл, то у вас не возникнет проблем.Вы также не можете знать, что у вас будет цикл во время компиляции, если вы создадите shared_ptrs во время выполнения.

Поэтому, пожалуйста, самостоятельно удаляйте ответы, в которых используется weak_ptr, потому что я специально просил не давать таких ответов...

Решение

Я не нашел гораздо лучшего метода, чем рисовать большие 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
};

Я просто решил добавить это к рассматриваемым классам и заглянуть в реестр.

(Идентификатор, если он задан как, например,'XYZ!' будет преобразован в строку.К сожалению, вы не можете указать строковую константу в качестве параметра шаблона)

Другие советы

shared_ptr представляет владение связь.Пока weak_ptr представляет осведомленность.Наличие нескольких объектов, владеющих друг другом, означает проблемы с архитектурой, которые решаются изменением одного или нескольких объектов. собственныйв осознавая's (то есть, weak_ptrх).

Я не понимаю, зачем предлагать weak_ptr считается бесполезным.

Я понимаю ваше раздражение по поводу того, что вам бойко говорят использовать слабый_ptr для разрыва циклических ссылок, и я сам почти испытываю ярость, когда мне говорят, что циклические ссылки — это плохой стиль программирования.

Вы конкретно спрашиваете, как вы распознаете циклические ссылки.Правда в том, что в сложном проекте некоторые опорные циклы являются косвенными и их трудно обнаружить.

Ответ заключается в том, что вам не следует делать ложных заявлений, которые делают вас уязвимыми для циклических ссылок.Я серьезно и критикую очень популярную практику — слепое использование общего_ptr для всего.

В вашем проекте должно быть ясно, какие указатели являются владельцами, а какие — наблюдателями.

Для владельцев используйтеshared_ptr

Для наблюдателей используйте слабые_ptr — все, а не только те, которые, по вашему мнению, могут быть частью цикла.

Если вы будете следовать этой практике, циклические ссылки не вызовут никаких проблем, и вам не придется о них беспокоиться.Конечно, вам придется написать много кода для преобразования всех этих слабых_птров в общие_птры, когда вы захотите их использовать — Boost действительно не подходит для этой работы.

Обнаружить циклы довольно легко:

установите счетчик на какое-то большое число, скажем, 1000 (точный размер зависит от вашего приложения)
начните с интересующего вас пионтера и следуйте указателям от него
для каждого указателя, которому вы следуете, уменьшите счетчик
если счетчик упадет до нуля до того, как вы достигнете конца цепочки указателей, у вас есть цикл

Однако это не очень полезно.И, как правило, невозможно решить проблему цикла для указателей с подсчетом ссылок - поэтому были изобретены альтернативные схемы сбора мусора, такие как очистка поколений.

Сочетание boost::weak_ptr и boost::shared_ptr может быть? Этот статья может быть интересна.

Смотрите этот пост на обнаружение циклов в графике.

Общее решение для поиска цикла можно найти здесь:

Лучший алгоритм для проверки наличия цикла в связанном списке

Это предполагает, что вы знаете структуру объектов в списке и можете следить за всеми указателями, содержащимися в каждом объекте.

Вероятно, вам нужен метод сбора мусора, такой как Марк и подметать.Идея этого алгоритма заключается в следующем:

Сохраните список со ссылками на все выделенные блоки памяти.
В какой-то момент вы запускаете сборщик мусора:
1. Сначала он отмечает все блоки, к которым у него еще есть доступ без использования списка ссылок.
2. Он проходит по списку, стирая каждый элемент, который не удалось пометить, подразумевая, что он больше недоступен и поэтому бесполезен.

Поскольку вы используете shared_ptr любые все еще существующие указатели, которых вам не удалось достичь, следует рассматривать как члены цикла.

Выполнение

Ниже я описываю очень наивный пример того, как реализовать sweep() часть алгоритма, но это будет reset() все остальные указатели на коллекторе.

Этот код хранит 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, и никаких утечек памяти или «все еще доступных» блоков обнаружено не было, так что, вероятно, он работает так, как ожидалось.

Некоторые замечания по этой реализации:

Вектор памяти будет расти бесконечно, вам следует использовать какой-то метод распределения памяти чтобы убедиться, что он не занимает всю вашу рабочую память.
Можно возразить, что нет необходимости использовать shared_ptr (который работает как сборщик мусора с подсчетом ссылок) для реализации такого сборщика мусора, поскольку алгоритм Mark and Sweep уже позаботится об этой работе.
Я не реализовал функцию mark(), потому что это усложнило бы пример, но это возможно, и я объясню это ниже.

Наконец, если вас интересует (2), такая реализация не является чем-то необычным.CPython (основная реализация Python) использует смесь подсчета ссылок, маркировки и очистки, но в основном для исторические причины.

Реализация `mark()` функция:

Для реализации mark() функции, вам нужно будет внести некоторые изменения:

Потребуется добавить bool marked; приписывать Cycle_t, и используйте его, чтобы проверить, отмечен ли указатель или нет.

Вам нужно будет написать 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();
      }
    }
  }
}

Это было длинное объяснение, но я надеюсь, что оно кому-то поможет.

Ответ на старый вопрос: вы можете попробовать навязчивый указатель, который может помочь подсчитать, сколько раз ссылается на ресурс.

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

Вот полученный результат.

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

Я знаю, вы сказали «нет слабого_птра», но почему бы и нет?Если ваша голова имеет слабый_ptr для хвоста и хвост со слабым_ptr для головы, это предотвратит цикл.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow

Как обнаружить циклы при использовании shared_ptr

Выполнение

Реализация mark() функция:

Реализация `mark()` функция: