A dangling pointer refers to an object whose lifetime has ended or whose storage is no longer valid. In a lock-free stack, one thread can remove and delete a node while another thread still holds its address. section 7.2.1
Two threads popping the same node
If two threads read the same head, one can remove and delete that node before the other dereferences its saved pointer. Leaving removed nodes undeleted avoids this particular dangling-pointer risk, but leaks memory. Split reference counts offer another approach: increase the external count before dereferencing, keeping the node valid during access. section 7.2.1 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%@!
Inspect the pop implementation’s reference-count increment before it accesses the node pointer. section 7.2.4
