An external reference count travels with a node pointer that multiple threads can access. It records references acquired through that shared pointer while a thread may still be using the node. Paired with a count inside the node, it lets a lock-free data structure delay deletion until no references remain. This is a manual alternative when shared-pointer operations do not provide a suitable lock-free implementation. section 7.2.4
In a lock-free stack, the two counts have different jobs:
- Store the external count beside the node pointer in a counted_node_ptr. The atomic head holds that pair; push initializes a new node’s external count to one. section 7.2.4
- Increase the external count atomically when acquiring a reference through head. A reader that finishes without removing the node releases its reference through the node’s internal count. section 7.2.4
- When the shared pointer/count pair is removed, transfer its remaining references to the internal count and discard the external count. Delete the node only when the internal count reaches zero. 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%@!
The stack declaration shows why the count and pointer form one atomic head value: another thread must not observe a pointer without the count associated with it. section 7.2.4
Why a queue needs another count
A queue push can load tail, then dereference it after another thread has advanced the queue and caused that node to be deleted. Giving tail an external count protects that access, but a node may also be referenced by the previous node’s next pointer. The queue therefore tracks how many external counters exist as well as its internal count. It deletes a node only when both values are zero. section 7.2.6
The count must be updated with atomic operations; merely placing an integer beside a pointer does not protect a concurrent read. The queue’s count-transfer and release paths also require careful handling: removing one external counter changes both the number of external counters and the internal count. section 7.2.4 section 7.2.6
