An internal reference count tracks references held by threads that have already accessed a node through an external pointer. In a lock-free stack, it works with an external count stored alongside the node pointer. Together, the two counts account for references that must be released before the node can be deleted. This split-count approach is useful when a suitable lock-free atomic shared pointer is unavailable. section 7.2.4
Consider a thread popping a stack node:
- It first increases the external count on the atomic head pointer. That protects the node while the thread attempts to use it. section 7.2.4
- When a reader finishes, it decreases the node’s internal count. Removing an external pointer transfers its remaining references into the internal count and discards that external counter. section 7.2.4
- The node can be deleted when its internal count reaches zero after the external pointer has been removed: no references remain outstanding. 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%@!
The stack pop implementation increments the head’s external count before dereferencing the node, then handles the reference after its head update attempt. section 7.2.4
A lock-free queue needs another safeguard: a node can have more than one external counter, including counters associated with head and tail. Its node counter therefore tracks both internal references and the number of external counters. These fields must be updated together to avoid races. Only when both reach zero is deletion safe. section 7.2.6
Listing 7.20. Freeing an external counter to a node in a lock-free queue
template<typename T>
class lock_free_queue
{
private:
static void free_external_counter(counted_node_ptr &old_node_ptr)
{
node* const ptr=old_node_ptr.ptr;
int const count_increase=old_node_ptr.external_count-2;
node_counter old_counter=
ptr->count.load(std::memory_order_relaxed);
node_counter new_counter;
do
{
new_counter=old_counter;
--new_counter.external_counters; #1
new_counter.internal_count+=count_increase; #2
}
while(!ptr->count.compare_exchange_strong( #3
old_counter,new_counter,
std::memory_order_acquire,std::memory_order_relaxed));
if(!new_counter.internal_count &&
!new_counter.external_counters)
{
delete ptr; #4
}
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":14,\"ch\":58},{\"line\":14,\"ch\":60}],[{\"line\":15,\"ch\":58},{\"line\":15,\"ch\":60}],[{\"line\":17,\"ch\":58},{\"line\":17,\"ch\":60}],[{\"line\":23,\"ch\":58},{\"line\":23,\"ch\":60}]]"}
!@%STYLE%@!
When the queue frees an external counter, it atomically decreases the number of external counters and transfers the appropriate references into the internal count. section 7.2.6
