CODEWITHSUNDEEP
c++multithreadingconcurrencymemory-leaks
Yariv Aridor
Yariv Aridor

Reputation: 1

Open issues with split reference counting example in the "c++ concurrency in action" book

I have two questions about listing 7.11 in section 7.2.4 of the "c++ concurrency in action" book (second edition). Following is a code snippet (from listing 7.11) for a lock-free stack implementation with explicit split reference counting mechanism to avoid memory leaks (I included only relevant code to my questions).

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;
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();
        while(!head.compare_exchange_weak(new_node.ptr->next,new_node));
    }
};

The reference counting mechanism is based on two counters: external_count and internal_count. The external_count is part of a wrapper (of type counted_node_ptr) to the stack nodes (of type node). The internal_count is kept inside the node structures.

Q1: In the push method, a new counted_node_ptr struct is created for a new item and finally it is pointed at by the head pointer (assume for simplicity that only one thread is doing push at a time). However, the counted_node_ptr struct is allocated on the stack so when push() is returned, head should be assumed to be a dangling pointer. Am I missing something here ?

Q2: The text says: "One possible technique involves the use of not one but two reference counts for each node: an internal count and an external count. The sum of these values is the total number of references to the node. The external count is kept alongside the pointer to the node and is increased every time the pointer is read. When the reader is finished with the node, it decreases the internal count. A simple operation that reads the pointer will leave the external count increased by one and the internal count decreased by one when it’s finished. When the external count/pointer pairing is no longer required (the node is no longer accessible from a location accessible to multiple threads), the internal count is increased by the value of the external count minus one and the external counter is discarded. Once the internal count is equal to zero, there are no outstanding references to the node and it can be safely deleted.".

I don't fully understand this scheme of reference counting using two counters: Why one counter is not sufficient? what each counter actually represents ? Does anyone have a reference (link) to a formal description of this scheme?

Upvotes: 0

Views: 119

Answers (1)

user10
user10

Reputation: 296

If your head is simply node pointer then on load you need atomically load head and then atomically increment internal_count. In between of head.load() and internal_count.fetch_add(1) something can happen so you need to lock and receive shared_ptr which is not lockfree. In simple load on node pointer:

 node* old_head=head.load();

You already use pointer but since internal_count not incremented yet nothing prevents from another thread to delete it.

In your example you use wrapper for node pointer not pointer itself so you need some external_count to safely access it. You increment external_count in copy of old_counter(new_counter) and if old_counter still head you replace head with incremented (owned) copy of old_counter in one atomic CAS :

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)); 
   old_counter.external_count=new_counter.external_count;
 }

So after increase_head_count you can safely access ptr.

Atomic internal_count you need to prevent race in std::shared_ptr<T> pop() between thread in if(head.compare_exchange_strong(old_head,ptr->next)) and thread in else if(ptr->internal_count.fetch_sub(1)==1)

Upvotes: 0

Related Questions