A Lock-Free Stack: A Hazard Pointer Implementation Explained II
In my last post, I started to explain a hazard pointer implementation: A Lock-Free Stack: A Hazard Pointer Implementation Explained I. Today, I will continue to explain the implementation.
The Retire List
The retire list has the public member functions isInUse, addNode, and deleteUnusedNodes. Additionally, it has the inner class RetireNode, an atomic member of it, and the private member function addToRetiredNodes.
template <typename T, Node MyNode = MyNode<T>>
class RetireList {
struct RetiredNode {
MyNode* node;
RetiredNode* next;
RetiredNode(MyNode* p) : node(p), next(nullptr) { }
~RetiredNode() {
delete node;
}
};
std::atomic<RetiredNode*> RetiredNodes;
void addToRetiredNodes(RetiredNode* retiredNode) {
retiredNode->next = RetiredNodes.load();
while (!RetiredNodes.compare_exchange_strong(retiredNode->next, retiredNode));
}
public:
bool isInUse(MyNode* node) {
for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
if (HazardPointers<T>[i].pointer.load() == node) return true;
}
return false;
}
void addNode(MyNode* node) {
addToRetiredNodes(new RetiredNode(node));
}
void deleteUnusedNodes() {
RetiredNode* current = RetiredNodes.exchange(nullptr);
while (current) {
RetiredNode* const next = current->next;
if (!isInUse(current->node)) delete current;
else addToRetiredNodes(current);
current = next;
}
}
};
Let’s start with the interface of the type RetireList.
The member function isInUse checks if node is in use. It does its job by traversing the variable template HazardPointers that is parameterized on the type of data the node holds. HazardPointers is a C-array of HazardPointer of length 50. A HazardPointer consists of an atomic thread id and an atomic pointer to a node.
constexpr std::size_t MaxHazardPointers = 50;
template <typename T, Node MyNode = MyNode<T>>
struct HazardPointer {
std::atomic<std::thread::id> id;
std::atomic<MyNode*> pointer;
};
template <typename T>
HazardPointer<T> HazardPointers[MaxHazardPointers];
Using an STL container such as std::set as HazardPointers is much more convenient. std::set is already ordered and guarantees constant access time on average but has a big issue: it’s not thread-safe.
The member function addNode takes a node, invokes the private member function addToRetiredNodes, and puts the node into an RetiredNode. RetiredNode is an RAII object and guarantees that the wrapped node is destroyed, releasing its memory. All retired nodes build a singly-linked list.
The member function deleteUnusedNodes traverses the singly-linked list of retired nodes by applying the following pattern:
void deleteUnusedNodes() {
RetiredNode* current = RetiredNodes.exchange(nullptr);
while (current) {
RetiredNode* const next = current->next;
if (!isInUse(current->node)) delete current;
else addToRetiredNodes(current);
current = next;
}
}
It checks the current node, points the next node to current->next and updates the current node with the next node. Finally, the current node is destroyed if not used anymore or added to the retired nodes. The private member function addToRetireNodes adds the retired nodes to the singly-linked list. To perform its job, it loads the RetiredNodes and makes the new node retiredNode to the new head of the singly-linked list. Before retiredNode becoming the new head of the singly-linked list, I have to ensure that it is still the head of the singly-linked list because another thread could kick in and change the head of the singly-linked list in the meantime. Thanks to the while-loop, retiredNode becomes only the new head if retiredNode->next = RetiredNodes.load() holds. If not, retiredNode->next is updated to RetiredNodes.load().
There is only one piece of the puzzle left:
The Hazard Pointer Owner
Recommended by LinkedIn
template <typename T, Node MyNode = MyNode<T>>
class HazardPointerOwner {
HazardPointer<T>* hazardPointer;
public:
HazardPointerOwner(HazardPointerOwner const &) = delete;
HazardPointerOwner operator=(HazardPointerOwner const &) = delete;
HazardPointerOwner() : hazardPointer(nullptr) {
for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
std::thread::id old_id;
if (HazardPointers<T>[i].id.compare_exchange_strong(
old_id, std::this_thread::get_id())) {
hazardPointer = &HazardPointers<T>[i];
break;
}
}
if (!hazardPointer) {
throw std::out_of_range("No hazard pointers available!");
}
}
std::atomic<MyNode*>& getPointer() {
return hazardPointer->pointer;
}
~HazardPointerOwner() {
hazardPointer->pointer.store(nullptr);
hazardPointer->id.store(std::thread::id());
}
};
HazardPointerOwner holds a hazardPointer. This hazardPointer is set in the constructor by traversing all HazardPointers. The compare_exchange_strong call checks in an atomic step if the currently traversed hazard pointer is not set and sets its id to the id of the now executed thread (std::this_thread::get_id()). In the success case, hazardPointer becomes the new hazard pointer returned to the client invoking the member function getPointer. When all of the hazard pointers of HazardPointers are used, the constructor throws a std::out_of_range exception. Finally, HazardPointerOwner‘s destructor sets the hazardPointer to its default state.
Modernes C++ Mentoring
Do you want to stay informed: Subscribe.
What’s Next?
In C++26, we will get hazard pointers. I will write about them in my next post.