Como detectar ciclos ao usar shared_ptr

Question

shared_ptr é uma referência contando ponteiro inteligente na biblioteca Boost.

O problema com a contagem de referência é que ele não pode dispor de ciclos. Eu estou querendo saber como um iria sobre como resolver isso em C ++.

Por favor, não sugestões como: "não fazem ciclos", ou "usar um weak_ptr"

Editar

Eu não gosto de sugestões que dizem usar apenas um weak_ptr porque, obviamente, se você sabe que vai criar um ciclo, então você não tem um problema. Você também não pode sabe que vai ter um ciclo em tempo de compilação se você gerar shared_ptrs durante a execução.

Então, por favor, auto respostas de exclusão que o uso weak_ptr neles porque eu pedi especificamente não ter esse tipo de respostas ...

Answer 1

Eu não encontrei um método muito melhor do que o desenho grandes gráficos UML e olhando para fora para ciclos.

Para depurar, eu uso um contador de instância indo para o registro, como este:

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

Eu só definidos para acrescentar que para as classes em questão, e ter um olhar para o registro.

(A ID, se for dada como por exemplo 'XYZ!' Será convertido para uma string. Infelizmente, não é possível especificar uma constante string como parâmetro do modelo)

Answer 2

shared_ptr representa propriedade relação. Enquanto weak_ptr representa consciência . Tendo vários objetos que possuem uns aos outros significa que você tem problemas com a arquitetura, que é resolvido alterando um ou mais própria é a ciente de 's (isto é, weak_ptr de).

Eu não entendo porque sugerindo weak_ptr é considerado inútil.

Answer 3

Eu compreendo a sua irritação por ter sido levianamente disse para uso weak_ptr para quebrar referências cíclicas e eu quase me sinto raiva quando me disseram que as referências cíclicas são estilo de programação ruim.

Seu pedir especificamente como você detectar referências cíclicas. A verdade é que, em um projeto complexo alguns ciclos de referência são indiretos e difícil de detectar.

A resposta é que você não deve fazer declarações falsas que deixá-lo vulnerável a referências cíclicas. Estou falando sério e eu estou criticando uma prática muito popular -. Cegamente usando shared_ptr para tudo

Você deve ser claro em seu projeto que os ponteiros são proprietários e que são observadores.

Para os proprietários de usar shared_ptr

Para os observadores usar weak_ptr -. Todos eles, não apenas aqueles que você acha que pode ser parte de um ciclo

Se você seguir esta prática, em seguida, as referências cíclicas não irá causar quaisquer problemas e você não precisa se preocupar com eles. Claro que você vai ter um monte de código para escrever para converter todos esses weak_ptrs para shared_ptrs quando você quiser usá-los -. Impulso realmente não é até o trabalho

Answer 4

É bastante fácil de detectar ciclos:

• definir uma contagem de um número bastante largo, digamos 1000 (tamanho exato depende da sua aplicação)
• começar com o pionter você está interessado em e siga os ponteiros com ele
• para cada ponteiro que você siga, diminuir a contagem
• se a contagem cai para zero antes de chegar ao final da cadeia ponteiro, você tem um ciclo

Não é, no entanto, muito útil. E não é geralmente possível para resolver o problema cycvle para ponteiros contou-ref -. É por isso que esquemas de lixo colection alternativas como a eliminação geração foram inventadas

Answer 5

A combinação de boost::weak_ptr e boost::shared_ptr talvez? Este artigo pode ser do seu interesse.

Answer 6

Veja este post no detectar ciclos em um gráfico.

Answer 7

A solução genérica para encontrar um ciclo pode ser encontrada aqui:

melhor algoritmo para testar se um ligado lista tem um ciclo

Isso pressupõe que você conhece a estrutura dos objetos na lista, e pode seguir todas as indicações contidas em cada objeto.

Answer 8

Você está provavelmente na necessidade de uma técnica de coletor de lixo, como Mark e varredura . A idéia deste algoritmo é:

1. Mantenha uma lista com referências a todos os blocos de memória alocados.
2. Em algum momento você iniciar o coletor de lixo:
   1. primeiras marcas todos os blocos que ainda pode acesso sem usar a lista de referência.
   2. Ele passa a lista apagando cada item que não puderam ser marcados, o que implica que não é acessível a mais por isso não é útil.

Uma vez que você estiver usando shared_ptr qualquer ponteiros ainda existentes que não chegarem devem ser considerados como membros de um ciclo.

Implementação

Abaixo descrevo um exemplo muito ingênua de como implementar a parte sweep() do algoritmo, mas vai reset() todos os ponteiros restantes no coletor.

Este código armazena shared_ptr<Cycle_t> ponteiros. O Collector classe é responsável por manter o controle de todos os ponteiros e excluí-los quando sweep() é executado.

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

Você pode então usá-lo como este:

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

Eu testei com Valgrind e sem vazamentos de memória ou "ainda alcançáveis" blocos foram listados, por isso é provavelmente funcionando como esperado.

Algumas notas sobre esta implementação:

1. O vector de memória vai crescer indefinidamente, você deve usar alguma técnica de alocação de memória para se certificar de que não ocupa toda a memória o seu trabalho.
2. Pode-se argumentar que não há necessidade de usar shared_ptr (que funciona como um GC contagem de referência) para implementar esse coletor de lixo desde o Mark e algoritmo de varredura já iria cuidar do trabalho.
3. Eu não implementar a marca () função porque iria complicar o exemplo, mas é possível e eu vou explicar abaixo.

Finalmente, se você está preocupado com (2), este tipo de implementação não é inédito. CPython (a principal implementação de Python) faz usar uma mistura de contagem de referência e Mark e varredura, mas principalmente para motivos históricos .

Implementar a função mark():

Para implementar a função mark() você vai precisar fazer algumas modificações:

Seria necessário para adicionar um atributo bool marked; para Cycle_t, e usá-lo para verificar se o ponteiro está marcada ou não.

Você vai precisar para escrever a função Collector::mark() que ficaria assim:

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

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

E, em seguida, você deve modificar a função sweep() para remover a marca se o ponteiro está marcada ou então reset() o ponteiro:

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

Foi uma longa explicação, mas espero que ajude alguém.

Answer 9

resposta para a velha pergunta, você pode experimentar o ponteiro intrusiva que pode ajudar a contar quantas vezes o recurso que está sendo referido.

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

Aqui está o resultado retornado.

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

Answer 10

Eu sei que você disse "não weak_ptr" mas por que não? Ter sua cabeça com um weak_ptr a cauda, ??cauda com um weak_ptr a cabeça vai impedir que o ciclo.