A Lock-Free Stack: A Hazard Pointer Implementation Explained I
In my last post, I presented a hazard pointer implementation: A Lock-Free Stack: A Hazard Pointer Implementation. Today, I will explain the implementation.
MyNode is a class template, parametrized by the type it holds: data. MyNode models the concept Node.
template <typename T>
concept Node = requires(T a) {
{T::data};
{ *a.next } -> std::same_as<T&>;
};
template <typename T>
struct MyNode {
T data;
MyNode* next;
MyNode(T d): data(d), next(nullptr){ }
};
Concepts are compile-time predicates. They put semantic constraints on template parameters. The concept Node requires member data and a pointer next that returns a Node. The program lockFreeStackHazardPointers.cpp types are essentially parametrized on the data member and the concept Node. MyNode models the concept Node. For example, here is the declaration of the LockFreeStack:
template<typename T, Node MyNode = MyNode<T>>
class LockFreeStack;
Let me continue my analysis of the program with the lock-free stack.
template<typename T, Node MyNode = MyNode<T>>
class LockFreeStack {
std::atomic<MyNode*> head;
RetireList<T> retireList;
public:
LockFreeStack() = default;
LockFreeStack(const LockFreeStack&) = delete;
LockFreeStack& operator= (const LockFreeStack&) = delete;
void push(T val) {
MyNode* const newMyNode = new MyNode(val);
newMyNode->next = head.load();
while( !head.compare_exchange_strong(newMyNode->next, newMyNode) );
}
T topAndPop() {
std::atomic<MyNode*>& hazardPointer = getHazardPointer<T>();
MyNode* oldHead = head.load();
do {
MyNode* tempMyNode;
do {
tempMyNode = oldHead;
hazardPointer.store(oldHead);
oldHead = head.load();
} while( oldHead != tempMyNode );
} while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) ;
if ( !oldHead ) throw std::out_of_range("The stack is empty!");
hazardPointer.store(nullptr);
auto res = oldHead->data;
if ( retireList.isInUse(oldHead) ) retireList.addNode(oldHead);
else delete oldHead;
retireList.deleteUnusedNodes();
return res;
}
};
The push call is not critical from a concurrency perspective because head is updated in an atomic step. Additionally, the compare_exchange_strong call guarantees that head is always the current head of the stack.
Due to hazard pointers, the call topAndPop becomes more complicated. First, the function getHazardPointer references the hazard pointer for the current thread. The call hazardPointer.store(oldHead) makes the current thread to the owner of the hazard pointer, and the call hazardPointer.store(nullptr)releases its ownership. First, let me analyze the inner and outer do-while loops. The inner do-while loop sets the hazard pointer to the head of the stack. The do-while loop ends when the following holds: oldHead == tempNode. Both nodes are equal if oldHead is still the current head of the lock-free stack. oldHead was set and could not be the current head anymore because another thread may be kicked in and already managed oldHead. The outer do-while loop should be familiar from the previous lock-free stack implementations. I iterate in the while loop using compare_exchange_strong and set the head to oldHead->next. In the end, head is the head of the stack. Remember, the member function topAndPop should return the value of the head and remove it. Before I use oldHead I have to check if oldHead is not a null pointer. If oldHead is a null pointer, I throw an exception. The rest of the topAndPop is straightforward. ?The call retireList.isInUse(oldHead) checks if oldHead is still in use. Depending on this check, oldHead is added to the retire list retireList.addNode if it is not yet on the list or deleted. The last call retireList.deleteUnusedNodes is the most labor-intensive call in the member function topAndPop. The member function retireListe.deleteUnusedNodes traverses the entire retire list and deletes all nodes that are not used anymore.
For performance reasons, the call retireList.deleteUnusedNodes should not be executed in each call of topAndPop. An improved strategy is to invoke the member function deleteUnusedNodes if the length of the retire list exceeds a specific threshold. For example, when the length of the retire list is twice the length of the stack, at least half of the nodes can be deleted. This threshold value is a trade-off between performance requirements and memory consumption.
Let me continue my explanation with the free function getHazardPointer.
template <typename T, Node MyNode = MyNode<T>>
sttd::atomic<MyNode*>& getHazardPointer() {
thread_local static HazardPointerOwner<T> hazard;
return hazard.getPointer();
}
The function getHazardPointer references a hazard pointer using the hazard pointer owner hazard. hazard is a thread-local and static variable. Therefore, each thread gets its copy of the hazard pointer owner, and its lifetime is bound to the lifetime of the owning thread. The bound lifetime of the hazard pointer owner is crucial because it guarantees the hazard pointer is cleared when the thread-local hazard pointer owner is destroyed. I write more about this RAII object in my analysis of the class type HazardPointerOwner.
What’s Next?
In my next post, I will explain the remaining implementation.
?
Modernes C++ Mentoring
Do you want to stay informed: Subscribe.
?