Removing a node from a lock-free stack does not necessarily make it safe to delete. Another thread may already have read the node’s address and be about to dereference it. Memory reclamation must account for those readers before releasing a removed node. section 7.2.3
Hazard pointers make a reader’s intended access visible. A thread stores the node’s address in its hazard pointer before dereferencing it, then clears the pointer when the access is finished. A thread removing a node checks the hazard pointers: if any still name that node, it defers deletion; otherwise, it can delete the node. Deferred nodes must be checked again later. section 7.2.3
std::shared_ptr<T> pop()
{
std::atomic<void*>& hp=get_hazard_pointer_for_current_thread();
node* old_head=head.load(); #1
node* temp;
do
{
temp=old_head;
hp.store(old_head); #2
old_head=head.load();
} while(old_head!=temp); #3
// ...
}
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":3,\"ch\":42},{\"line\":3,\"ch\":44}],[{\"line\":8,\"ch\":42},{\"line\":8,\"ch\":44}],[{\"line\":10,\"ch\":42},{\"line\":10,\"ch\":44}]]"}
!@%STYLE%@!
Publishing a hazard pointer is not enough on its own. The reader reloads the stack head and repeats if it changed, because the original node could have been removed between the first load and publication. section 7.2.3
Listing 7.6. An implementation of pop() using hazard pointers
std::shared_ptr<T> pop()
{
std::atomic<void*>& hp=get_hazard_pointer_for_current_thread();
node* old_head=head.load();
do
{
node* temp;
do #1
{
temp=old_head;
hp.store(old_head);
old_head=head.load();
} while(old_head!=temp);
}
while(old_head &&
!head.compare_exchange_strong(old_head,old_head->next));
hp.store(nullptr); #2
std::shared_ptr<T> res;
if(old_head)
{
res.swap(old_head->data);
if(outstanding_hazard_pointers_for(old_head)) #3
{
reclaim_later(old_head); #4
}
else
{
delete old_head; #5
}
delete_nodes_with_no_hazards(); #6
}
return res;
}
The pop operation validates the protected head, attempts to remove it, clears its hazard pointer, and either deletes the removed node or passes it to reclaim_later() according to other threads’ hazard pointers. section 7.2.3
The supporting machinery also matters: each participating thread needs a hazard-pointer location visible to other threads. A simple implementation uses a fixed array of slots claimed by thread ID; its finite capacity makes slot allocation a design constraint. Deferred nodes can be linked onto an atomic reclamation list with a deleter for their type. section 7.2.3
Listing 7.8. A simple implementation of the reclaim functions
template<typename T>
void do_delete(void* p)
{
delete static_cast<T*>(p);
}
struct data_to_reclaim
{
void* data;
std::function<void(void*)> deleter;
data_to_reclaim* next;
template<typename T>
data_to_reclaim(T* p): #1
data(p),
deleter(&do_delete<T>),
next(0)
{}
~data_to_reclaim()
{
deleter(data); #2
}
};
std::atomic<data_to_reclaim*> nodes_to_reclaim;
void add_to_reclaim_list(data_to_reclaim* node) #3
{
node->next=nodes_to_reclaim.load();
while(!nodes_to_reclaim.compare_exchange_weak(node->next,node));
}
template<typename T>
void reclaim_later(T* data) #4
{
add_to_reclaim_list(new data_to_reclaim(data)); #5
}
void delete_nodes_with_no_hazards()
{
data_to_reclaim* current=nodes_to_reclaim.exchange(nullptr); #6
while(current)
{
data_to_reclaim* const next=current->next;
if(!outstanding_hazard_pointers_for(current->data)) #7
{
delete current; #8
}
else
{
add_to_reclaim_list(current); #9
}
current=next;
}
}
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":11,\"ch\":66},{\"line\":11,\"ch\":68}],[{\"line\":18,\"ch\":66},{\"line\":18,\"ch\":68}],[{\"line\":22,\"ch\":66},{\"line\":22,\"ch\":68}],[{\"line\":28,\"ch\":66},{\"line\":28,\"ch\":68}],[{\"line\":30,\"ch\":66},{\"line\":30,\"ch\":68}],[{\"line\":34,\"ch\":66},{\"line\":34,\"ch\":68}],[{\"line\":38,\"ch\":66},{\"line\":38,\"ch\":68}],[{\"line\":40,\"ch\":66},{\"line\":40,\"ch\":68}],[{\"line\":44,\"ch\":66},{\"line\":44,\"ch\":68}]]"}
!@%STYLE%@!
A deferred-reclamation record keeps both the object address and a deleter. The records are added to an atomic list rather than immediately deleting objects that may still be in use. section 7.2.3
Reference counting offers a different test: track how many threads may be accessing each node. Using std::shared_ptr<node> can simplify ownership, but its atomic operations are not guaranteed to be lock-free. std::experimental::atomic_shared_ptr<T> supplies atomic shared-pointer operations where the Concurrency TS is available; it, too, may or may not be lock-free on a given implementation. When neither option is lock-free, split reference counts provide another approach, with an external count in the pointer and an internal count in the node. 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 split-count stack stores an external count alongside each node pointer and an atomic internal count in the node. This makes the accounting explicit rather than relying on lock-free shared-pointer operations. section 7.2.4
