In concurrent data structures, reference counting tracks how many threads access each node so a node can be reclaimed when it is no longer in use. Unlike hazard pointers, which record nodes in use, this approach maintains a count. Managing the counts safely is difficult: std::shared_ptr operations are not guaranteed to be lock-free, and using atomic operations consistently is challenging. section 7.2.4
Lock-free stack examples show several approaches:
- Use atomic operations on std::shared_ptr when the implementation guarantees they are lock-free; clear a popped node’s next pointer to avoid deeply nested destruction. section 7.2.4
- Use std::experimental::atomic_shared_ptr<T> from the Concurrency TS to handle reference counting alongside atomic operations. section 7.2.4
- Split reference counts across external and internal counters in a stack implementation. section 7.2.4
Listing 7.11. Pushing a node on a lock-free stack using split reference counts
template<typename T>
class lock_free_stack
{
private:
struct node;
struct counted_node_ptr #1
{
int external_count;
node* ptr;
};
struct node
{
std::shared_ptr<T> data;
std::atomic<int> internal_count; #2
counted_node_ptr next; #3
node(T const& data_):
data(std::make_shared<T>(data_)),
internal_count(0)
{}
};
std::atomic<counted_node_ptr> head; #4
public:
~lock_free_stack()
{
while(pop());
}
void push(T const& data) #5
{
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));
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":5,\"ch\":45},{\"line\":5,\"ch\":47}],[{\"line\":13,\"ch\":45},{\"line\":13,\"ch\":47}],[{\"line\":14,\"ch\":45},{\"line\":14,\"ch\":47}],[{\"line\":20,\"ch\":45},{\"line\":20,\"ch\":47}],[{\"line\":26,\"ch\":45},{\"line\":26,\"ch\":47}]]"}
!@%STYLE%@!
See the stack’s counted-node structure, with separate external and internal counts. section 7.2.4
Listing 7.12. Popping a node from a lock-free stack using split reference counts
template<typename T>
class lock_free_stack
{
private:
// other parts as in listing 7.11
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)); #1
old_counter.external_count=new_counter.external_count;
}
public:
std::shared_ptr<T> pop()#
{
counted_node_ptr old_head=head.load();
for(;;)
{
increase_head_count(old_head);
node* const ptr=old_head.ptr; #2
if(!ptr)
{
return std::shared_ptr<T>();
}
if(head.compare_exchange_strong(old_head,ptr->next)) #3
{
std::shared_ptr<T> res;
res.swap(ptr->data); #4
int const count_increase=old_head.external_count-2; #5
if(ptr->internal_count.fetch_add(count_increase)== #6
-count_increase)
{
delete ptr;
}
return res; #7
}
else if(ptr->internal_count.fetch_sub(1)==1)
{
delete ptr; #8
}
}
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":13,\"ch\":72},{\"line\":13,\"ch\":74}],[{\"line\":23,\"ch\":72},{\"line\":23,\"ch\":74}],[{\"line\":28,\"ch\":72},{\"line\":28,\"ch\":74}],[{\"line\":31,\"ch\":72},{\"line\":31,\"ch\":74}],[{\"line\":32,\"ch\":72},{\"line\":32,\"ch\":74}],[{\"line\":33,\"ch\":72},{\"line\":33,\"ch\":74}],[{\"line\":38,\"ch\":72},{\"line\":38,\"ch\":74}],[{\"line\":42,\"ch\":72},{\"line\":42,\"ch\":74}]]"}
!@%STYLE%@!
See how the stack increases the head count and uses it while popping a node. section 7.2.4
