A hazard pointer is a thread’s public indication that it may access an object. Deleting a node while another thread still holds and uses a pointer to it causes undefined behavior. Hazard pointers let a lock-free data structure reclaim individual nodes without waiting for every thread to leave an operation. section 7.2.3 section 7.2.2
In a lock-free stack’s pop() operation, protection and reclamation follow this sequence:
- Load the head, publish it in the current thread’s hazard pointer, then load the head again. If it changed, repeat before accessing the node. section 7.2.3
- Attempt to remove the protected head with compare_exchange_strong. Retry if another thread changed the head; clear the hazard pointer once protection is no longer needed. section 7.2.3
- Before deleting the removed node, scan for hazard pointers that still reference it. Delete it if none do; otherwise place it on a list for later checks. 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() implementation puts publication and head validation inside the removal retry loop. After removal, it clears its hazard pointer and chooses between immediate deletion and reclaim_later(). section 7.2.3
The first head load alone is not enough: another thread might remove that node before the hazard pointer is published. Reloading and comparing the head checks that the published pointer still protects the node being considered. A removed node may still be in use by a thread that published it earlier, so removal does not itself make deletion safe. section 7.2.3
Listing 7.7. A simple implementation of get_hazard_pointer_for_current_thread()
unsigned const max_hazard_pointers=100;
struct hazard_pointer
{
std::atomic<std::thread::id> id;
std::atomic<void*> pointer;
};
hazard_pointer hazard_pointers[max_hazard_pointers];
class hp_owner
{
hazard_pointer* hp;
public:
hp_owner(hp_owner const&)=delete;
hp_owner operator=(hp_owner const&)=delete;
hp_owner():
hp(nullptr)
{
for(unsigned i=0;i<max_hazard_pointers;++i)
{
std::thread::id old_id;
if(hazard_pointers[i].id.compare_exchange_strong( #1
old_id,std::this_thread::get_id()))
{
hp=&hazard_pointers[i];
break;
}
}
if(!hp) #2
{
throw std::runtime_error("No hazard pointers available");
}
}
std::atomic<void*>& get_pointer()
{
return hp->pointer;
}
~hp_owner() #3
{
hp->pointer.store(nullptr);
hp->id.store(std::thread::id());
}
};
std::atomic<void*>& get_hazard_pointer_for_current_thread() #4
{
thread_local static hp_owner hazard; #5
return hazard.get_pointer(); #6
}
One simple storage scheme provides a fixed array of hazard-pointer records. A thread claims a record by comparing and exchanging its thread ID; the shown implementation throws if no record is available. section 7.2.3
This addresses a weakness of waiting for a quiescent period: under sustained calls to pop(), there may never be a moment when no thread is inside it, and a pending-deletion list can grow without bound. Hazard pointers instead ask whether a particular node is still protected. They require publicly visible pointer records, a scan before deletion, and a way to revisit deferred nodes. section 7.2.2 section 7.2.3
