{"id":10715,"date":"2025-04-07T11:11:06","date_gmt":"2025-04-07T11:11:06","guid":{"rendered":"https:\/\/www.modernescpp.com\/?p=10715"},"modified":"2025-07-03T14:40:14","modified_gmt":"2025-07-03T14:40:14","slug":"a-lock-free-stack-a-hazard-pointer-implementation-explained-ii","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/a-lock-free-stack-a-hazard-pointer-implementation-explained-ii\/","title":{"rendered":"A Lock-Free Stack: A Hazard Pointer Implementation Explained II"},"content":{"rendered":"\n

In my last post, I started to explain a hazard pointer implementation: A Lock-Free Stack: A Hazard Pointer Implementation Explained I<\/a>. Today, I will continue to explain the implementation.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

The Retire List<\/h2>\n\n\n\n

The retire list has the public member functions isInUse<\/code>, addNode<\/code>, and deleteUnusedNodes<\/code>. Additionally, it has the inner class RetireNode<\/code>, an atomic member of it, and the private member function addToRetiredNodes<\/code>. <\/p>\n\n\n\n

template<\/span> <<\/span>typename<\/span> T, Node MyNode =<\/span> MyNode<<\/span>T>><\/span>\nclass<\/span> RetireList<\/span> {\n\n    struct<\/span> RetiredNode {\n        MyNode*<\/span> node;\n        RetiredNode*<\/span> next;\n        RetiredNode(MyNode*<\/span> p) :<\/span> node(p), next(nullptr) { }\n        ~<\/span>RetiredNode() {\n            delete<\/span> node;\n        }\n    };\n\n    std::<\/span>atomic<<\/span>RetiredNode*><\/span> RetiredNodes;\n\n    void<\/span> addToRetiredNodes<\/span>(RetiredNode*<\/span> retiredNode) {\n        retiredNode-><\/span>next =<\/span> RetiredNodes.load();\n        while<\/span> (!<\/span>RetiredNodes.compare_exchange_strong(retiredNode-><\/span>next, retiredNode));\n    }\n\n public:<\/span>\n\n    bool<\/span> isInUse<\/span>(MyNode*<\/span> node) {\n        for<\/span> (std::<\/span>size_t<\/span> i =<\/span> 0<\/span>; i <<\/span> MaxHazardPointers; ++<\/span>i) {\n            if<\/span> (HazardPointers<<\/span>T><\/span>[i].pointer.load() ==<\/span> node) return<\/span> true<\/span>;\n        }\n        return<\/span> false<\/span>;\n    }\n\n    void<\/span> addNode<\/span>(MyNode*<\/span> node) {\n        addToRetiredNodes(new<\/span> RetiredNode(node));\n    }\n\n    void<\/span> deleteUnusedNodes<\/span>() {\n        RetiredNode*<\/span> current =<\/span> RetiredNodes.exchange(nullptr);\n        while<\/span> (current) {\n            RetiredNode*<\/span> const<\/span> next =<\/span> current-><\/span>next;\n            if<\/span> (!<\/span>isInUse(current-><\/span>node)) delete<\/span> current;\n            else<\/span> addToRetiredNodes(current);\n            current =<\/span> next;\n        }\n    }\n};\n<\/pre><\/div>\n\n\n\n
Let’s start with the interface of the type RetireList<\/code>.<\/p>\n\n\n\n
The member function isInUse<\/code> checks if node <\/code>is in use. It does its job by traversing the variable template<\/a> HazardPointers <\/code>that is parameterized on the type of data the node holds. HazardPointers <\/code>is a C-array of HazardPointer <\/code>of length 50. A HazardPointer <\/code>consists of an atomic thread id <\/code>and an atomic pointer <\/code>to a node.<\/p>\n\n\n\n
constexpr std::<\/span>size_t<\/span> MaxHazardPointers =<\/span> 50<\/span>;\n\ntemplate<\/span> <<\/span>typename<\/span> T, Node MyNode =<\/span> MyNode<<\/span>T>><\/span>\nstruct<\/span> HazardPointer {\n    std::<\/span>atomic<<\/span>std::<\/span>thread<\/span>::<\/span>id><\/span> id;\n    std::<\/span>atomic<<\/span>MyNode*><\/span> pointer;\n};\n\ntemplate<\/span> <<\/span>typename<\/span> T><\/span>\nHazardPointer<<\/span>T><\/span> HazardPointers[MaxHazardPointers];\n<\/pre><\/div>\n\n\n\n
Using an STL container such as std::set <\/code>as HazardPointers <\/code>is much more convenient. std::set <\/code>is already ordered and guarantees constant access time on average but has a big issue: it’s not thread-safe.<\/p>\n\n\n\n
The member function addNode <\/code>takes a node, invokes the private member function addToRetiredNodes<\/code>, and puts the node into an RetiredNode. RetiredNode <\/code> is an RAII object and guarantees that the wrapped node is destroyed, releasing its memory. All retired nodes build a singly-linked list.<\/p>\n\n\n\n
The member function deleteUnusedNodes <\/code>traverses the singly-linked list of retired nodes by applying the following pattern:<\/p>\n\n\n\n
    void<\/span> deleteUnusedNodes<\/span>() {\n        RetiredNode*<\/span> current =<\/span> RetiredNodes.exchange(nullptr);\n        while<\/span> (current) {\n            RetiredNode*<\/span> const<\/span> next =<\/span> current-><\/span>next;\n            if<\/span> (!<\/span>isInUse(current-><\/span>node)) delete<\/span> current;\n            else<\/span> addToRetiredNodes(current);\n            current =<\/span> next;\n        }\n    }\n<\/pre><\/div>\n\n\n\n
It checks the current node, points the next node to current->next<\/code> 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 <\/code>adds the retired nodes to the singly-linked list. To perform its job, it loads the RetiredNodes <\/code>and makes the new node retiredNode <\/code>to the new head of the singly-linked list. Before retiredNode <\/code>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 <\/code>becomes only the new head if retiredNode->next = RetiredNodes.load()<\/code> holds. If not, retiredNode->next<\/code> is updated to RetiredNodes.load().<\/code><\/p>\n\n\n\n
There is only one piece of the puzzle left:<\/p>\n\n\n\n
The Hazard Pointer Owner <\/h2>\n\n\n\n
template<\/span> <<\/span>typename<\/span> T, Node MyNode =<\/span> MyNode<<\/span>T>><\/span>\nclass<\/span> HazardPointerOwner<\/span> {\n\n    HazardPointer<<\/span>T>*<\/span> hazardPointer;\n\n public:<\/span>\n    HazardPointerOwner(HazardPointerOwner const<\/span> &<\/span>) =<\/span> delete<\/span>;\n    HazardPointerOwner operator<\/span>=<\/span>(HazardPointerOwner const<\/span> &<\/span>) =<\/span> delete<\/span>;\n\n    HazardPointerOwner() :<\/span> hazardPointer(nullptr) {\n        for<\/span> (std::<\/span>size_t<\/span> i =<\/span> 0<\/span>; i <<\/span> MaxHazardPointers; ++<\/span>i) {\n            std::<\/span>thread<\/span>::<\/span>id old_id;\n            if<\/span> (HazardPointers<<\/span>T><\/span>[i].id.compare_exchange_strong(\n                                        old_id, std::<\/span>this_thread::<\/span>get_id())) {\n                hazardPointer =<\/span> &<\/span>HazardPointers<<\/span>T><\/span>[i];\n                break<\/span>;\n            }\n        }\n        if<\/span> (!<\/span>hazardPointer) {\n            throw<\/span> std::<\/span>out_of_range("No hazard pointers available!"<\/span>);\n        }\n    }\n\n    std::<\/span>atomic<<\/span>MyNode*>&<\/span> getPointer() {\n        return<\/span> hazardPointer-><\/span>pointer;\n    }\n\n    ~<\/span>HazardPointerOwner() {\n        hazardPointer-><\/span>pointer.store(nullptr);\n        hazardPointer-><\/span>id.store(std::<\/span>thread<\/span>::<\/span>id());\n    }\n};\n<\/pre><\/div>\n\n\n\n
 HazardPointerOwner <\/code>holds a hazardPointer<\/code>. This hazardPointer <\/code>is set in the constructor by traversing all HazardPointers<\/code>. The compare_exchange_strong <\/code>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()<\/code>). In the success case, hazardPointer <\/code>becomes the new hazard pointer returned to the client invoking the member function getPointer<\/code>. When all of the hazard pointers of HazardPointers <\/code>are used, the constructor throws a std::out_of_range <\/code>exception. Finally, HazardPointerOwner<\/code>‘s destructor sets the hazardPointer <\/code>to its default state.<\/p>\n\n\n\n
What’s Next?<\/h2>\n\n\n\n
In C++26, we will get hazard pointers. I will write about them in my next post.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":21,"featured_media":10580,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[559],"tags":[563],"class_list":["post-10715","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c26-blog","tag-hazard-pointers"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10715","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=10715"}],"version-history":[{"count":3,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10715\/revisions"}],"predecessor-version":[{"id":10719,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10715\/revisions\/10719"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/10580"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=10715"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=10715"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=10715"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}