無鎖堆棧引用計數

Question

從回答我剛纔的問題： Pointers in c++ after delete

它變得清晰，即使用指針的值，即點「刪除」記憶（尤其是將它們複製）導致在C++ 11中的undef行爲和在C++ 14中的實現定義的行爲。

Antomy威廉姆斯在他的著作「C++在行動併發」建議用引用計數的下一個無鎖堆棧：

#include <atomic> 
#include <memory> 

template<typename T> 
class lock_free_stack 
{ 
private: 
    struct node; 
    struct counted_node_ptr 
    { 
     int external_count; 
     node* ptr; 
    }; 
    struct node 
    { 
     std::shared_ptr<T> data; 
     std::atomic<int> internal_count; 
     counted_node_ptr next; 
     node(T const& data_): 
      data(std::make_shared<T>(data_)), 
      internal_count(0) 
     {} 
    }; 
    std::atomic<counted_node_ptr> head; 
    void increase_head_count(counted_node_ptr& old_counter) 
    { 
     counted_node_ptr new_counter; 
     do 
     { 
      new_counter=old_counter; 
      ++new_counter.external_count; 
     } 
     while(!head.compare_exchange_strong(
        old_counter,new_counter, 
        std::memory_order_acquire, 
        std::memory_order_relaxed)); 
     old_counter.external_count=new_counter.external_count; 
    } 
public: 
    ~lock_free_stack() 
    { 
     while(pop()); 
    } 
    void push(T const& data) 
    { 
     counted_node_ptr new_node; 
     new_node.ptr=new node(data); 
     new_node.external_count=1; 
     new_node.ptr->next=head.load(std::memory_order_relaxed) 
      while(!head.compare_exchange_weak(
         new_node.ptr->next,new_node, 
         std::memory_order_release, 
         std::memory_order_relaxed)); 
    } 
    std::shared_ptr<T> pop() 
    { 
     counted_node_ptr old_head= 
      head.load(std::memory_order_relaxed); 
     for(;;) 
     { 
      increase_head_count(old_head); 
      node* const ptr=old_head.ptr; 
      if(!ptr) 
      { 
       return std::shared_ptr<T>(); 
      } 
      if(head.compare_exchange_strong(
        old_head,ptr->next,std::memory_order_relaxed)) 
      { 
       std::shared_ptr<T> res; 
       res.swap(ptr->data); 
       int const count_increase=old_head.external_count-2; 
       if(ptr->internal_count.fetch_add(
         count_increase,std::memory_order_release)==-count_increase) 
       { 
        delete ptr; 
       } 
       return res; 
      } 
      else if(ptr->internal_count.fetch_add(
         -1,std::memory_order_relaxed)==1) 
      { 
       ptr->internal_count.load(std::memory_order_acquire); 
       delete ptr; 
      } 
     } 
    } 
}; 

我擔心功能

void increase_head_count(counted_node_ptr& old_counter) 
{ 
    counted_node_ptr new_counter; 
    do 
    { 
     new_counter=old_counter; 
     ++new_counter.external_count; 
    } 
    while(!head.compare_exchange_strong(
       old_counter,new_counter, 
       std::memory_order_acquire, 
       std::memory_order_relaxed)); 
    old_counter.external_count=new_counter.external_count; 
} 

看來，這new_counter = old_counter;可以在old_counter.ptr被另一個線程刪除時執行。

那麼，有人可以確認或拒絕，這個堆棧實現在C++ 11中嚴格不正確嗎？

Answer 1

這是可能的，但沒有問題，因爲compare_exchange呼叫將檢測到並丟棄new_counter。