Stos bez blokad

Question

Czytając książkę o przetwarzaniu współbieżnym natrafiłem na fragment który mówi o konieczności pozbycia się wskaźnika next z usuwanego węzła aby uniknąć potencjalnego niebezpieczeństwa głęboko zagnieżdżonego uszkodzenia węzłów po usunięciu ostatniego egzemplarza std::shared_ptr który odwołuje się do danego węzła. Czy mógłby ktoś wytłumaczyć w jakiej okoliczności występuje ten błąd poniżej umieszczam kod tej klasy stosu problematyczna linijka znajduje się w funkcji pop

template<typename T>
class lock_free_stack
{
private:
    struct node
    {
        std::shared_ptr<T> data;
        std::shared_ptr<node> next;
        node(T const& data_):
            data(std::make_shared<T>(data_))
        {}
    };
    std::shared_ptr<node> head;
public:
    void push(T const& data)
    {
        std::shared_ptr<node> const new_node=std::make_shared<node>(data);
        new_node->next=std::atomic_load(&head);
        while(!std::atomic_compare_exchange_weak(&head,
                  &new_node->next,new_node));
    }
    std::shared_ptr<T> pop()
    {
        std::shared_ptr<node> old_head=std::atomic_load(&head);
        while(old_head && !std::atomic_compare_exchange_weak(&head,
                  &old_head,std::atomic_load(&old_head->next)));
        if(old_head)  {
            std::atomic_store(&old_head->next,std::shared_ptr<node>());
            return old_head->data;
        }
        return std::shared_ptr<T>();
    }
    ~lock_free_stack(){
        while(pop());
    }
};

 

 

 

Answer 1

Czy ten pop() jest efektywny? Nawet w destruktorze masz pętlę która wołając pop() przechodzi po liście kilkukrotnie (okolice while czyli linia 25). Oczywiście jeśli to wymaganie, nie mam uwag (ale jak trzymasz head, można poświęcić jeden wskaźnik także na tail to będziesz miał lepszą efektywność pop().. nie będziesz robił malarza Shlemiel'a: https://www.joelonsoftware.com/2001/12/11/back-to-basics/ ).

Pytasz o łańcuch destrukcji wynikający z lawiny wywołań usunięcia wskaźnika inteligentnego, który wywołuje usunięcie następnego .. itd. Łatwo wtedy zauważyć że każde z wywołań odłoży na stos powrót do elementu szczytowego. Stąd może wystąpić przepełnienie stosu (stack overflow). Tu masz to przystępnie opisane: https://www.codeproject.com/Questions/321104/Shared-Pointers-Deallocation

Tu w formie wizualnej jeszcze więcej: https://www.youtube.com/watch?v=JfmTagWcqoE

BTW. Używasz atomic trochę bez świadomości wydajności. One ogólnie nie mają sensu wydajnościowo (a głównie po to są) bez memory order https://en.cppreference.com/w/cpp/atomic/memory_order. Polecam: https://www.youtube.com/watch?v=ZQFzMfHIxng

Comments

Chyba nawet w innym wątku sugerowałem mu, że te usuwanie w destruktorze następnego elementu listy (bo tam o listę chodziło) jest ryzykowne.