{"id":10682,"date":"2025-03-10T11:42:17","date_gmt":"2025-03-10T11:42:17","guid":{"rendered":"https:\/\/www.modernescpp.com\/?p=10682"},"modified":"2025-07-03T14:37:49","modified_gmt":"2025-07-03T14:37:49","slug":"a-lock-free-stack-a-hazard-pointer-implementation","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/a-lock-free-stack-a-hazard-pointer-implementation\/","title":{"rendered":"A Lock-Free Stack: A Hazard Pointer Implementation"},"content":{"rendered":"\n

Hazard Pointers solve all issues of the previous implementation: A Lock-Free Stack: A Simple Garbage Collector<\/a>.<\/p>\n\n\n\n

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

From one Week to two Weeks <\/h2>\n\n\n\n

You may have already noticed. I will change my blog publishing frequency from one to two weeks in the future. Writing a post using your voice is exceptionally exhausting and time-consuming.<\/p>\n\n\n\n

Hazard Pointers<\/h2>\n\n\n\n

The term hazard pointers goes back to Maged Michael. Hazard pointers solve the classical problem of lock-free data structures such as a lock-free stack: When can a thread safely delete a node of a data structure while other threads can use this node at the same time?<\/p>\n\n\n\n


Although a hazard pointer provides a general solution for the common problem of safe memory
reclamation in lock-free data structures, I want to present it from the perspective of our lock-free
stack.<\/p>\n\n\n\n

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

<\/p>\n\n\n\n

A hazard pointer is a single-writer, multi-reader pointer. All hazard pointers build a linked list and are initialized with a null pointer. When a thread uses a stack node, it puts the node\u2019s address into a hazard pointer, indicating that it uses this node and is the exclusive owner of the used hazard pointer. When the thread is done using the node, it sets the hazard pointer to a null pointer and, therefore, releases its ownership. A thread keeps a list of hazard pointers standing for the nodes the thread is using and can not be deleted. When a thread wants to delete a node, it traverses the list of all hazard pointers and checks if the node is used. If the node is not in use, it deletes it. If the node is in use, it will eventually be put on a retire list of the to-be-deleted nodes. Eventually, the node is only added to the retire list if it is not yet on the list.<\/p>\n\n\n\n

This is the case for our lock-free stack. The member function topAndPop has two jobs regarding memory reclamation. First, it manages the to-be-deleted node; second, it traverses the retire list of nodes and deletes them if they aren\u2019t used anymore.<\/p>\n\n\n\n


I need the following member function in a new implementation of topAndPop <\/code>based on the previous description: getHazardPointer <\/code>to get a reference to a hazard pointer, retireList.addNode<\/code>, and retireList.deleteUnusedNodes<\/code> to add a node to the retire list retireList<\/code>. Additionally, retireList.deleteUnusedNodes<\/code> to delete all nodes from the retire list that are no longer used. Additionally, the member function retireList.deleteUnusedNode<\/code> uses the helper function retireList.isInUse <\/code>to decide if a node is currently used. The member function isInUse<\/code> is also handy in topAndPop <\/code>decide whether the current node should be added to the retire list or directly deleted.<\/p>\n\n\n\n

What does this mean for my previous LockFreeStack <\/code>implementation (
A Lock-Free Stack: A Complete Implementation<\/a>) without memory reclamation? Let\u2019s see. The following program shows the lock-free stack implementation based on hazard pointers.
<\/p>\n\n\n\n

A Hazard Pointer Implementation<\/h3>\n\n\n\n
\/\/ lockFreeStackHazardPointers.cpp<\/span>\n\n#include <atomic><\/span>\n#include <cstddef><\/span>\n#include <future><\/span>\n#include <iostream><\/span>\n#include <stdexcept><\/span>\n#include <thread><\/span>\n\ntemplate<\/span> <<\/span>typename<\/span> T><\/span>\nconcept Node =<\/span> requires(T a) {\n    {T::<\/span>data};\n    { *<\/span>a.next } -><\/span> std::<\/span>same_as<<\/span>T&><\/span>;\n};\n\ntemplate<\/span> <<\/span>typename<\/span> T><\/span>\nstruct<\/span> MyNode {\n    T data;\n    MyNode*<\/span> next;\n    MyNode(T d):<\/span> data(d), next(nullptr){ }\n};\n\nconstexpr 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\ntemplate<\/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\ntemplate<\/span> <<\/span>typename<\/span> T, Node MyNode =<\/span> MyNode<<\/span>T>><\/span>\nstd::<\/span>atomic<<\/span>MyNode*>&<\/span> getHazardPointer() {\n    thread_local static<\/span> HazardPointerOwner<<\/span>T><\/span> hazard;\n    return<\/span> hazard.getPointer();\n}\n\ntemplate<\/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};\n\ntemplate<\/span><<\/span>typename<\/span> T, Node MyNode =<\/span> MyNode<<\/span>T>><\/span>\nclass<\/span> LockFreeStack<\/span> {\n\n    std::<\/span>atomic<<\/span>MyNode*><\/span> head;\n    RetireList<<\/span>T><\/span> retireList;\n \n public:<\/span>\n    LockFreeStack() =<\/span> default<\/span>;\n    LockFreeStack(const<\/span> LockFreeStack&<\/span>) =<\/span> delete<\/span>;\n    LockFreeStack&<\/span> operator<\/span>=<\/span> (const<\/span> LockFreeStack&<\/span>) =<\/span> delete<\/span>;\n   \n    void<\/span> push<\/span>(T val) {\n        MyNode*<\/span> const<\/span> newMyNode =<\/span> new<\/span> MyNode(val);\n        newMyNode-><\/span>next =<\/span> head.load();\n        while<\/span>( !<\/span>head.compare_exchange_strong(newMyNode-><\/span>next, newMyNode) );\n    }\n\n    T topAndPop<\/span>() {\n        std::<\/span>atomic<<\/span>MyNode*>&<\/span> hazardPointer =<\/span> getHazardPointer<<\/span>T><\/span>();\n        MyNode*<\/span> oldHead =<\/span> head.load();\n        do<\/span> {\n            MyNode*<\/span> tempMyNode; \n            do<\/span> {\n                tempMyNode =<\/span> oldHead;\n                hazardPointer.store(oldHead);\n                oldHead =<\/span> head.load();\n            } while<\/span>( oldHead !=<\/span> tempMyNode );\n        } while<\/span>( oldHead &&<\/span> !<\/span>head.compare_exchange_strong(oldHead, oldHead-><\/span>next) ) ;\n        if<\/span> ( !<\/span>oldHead ) throw<\/span> std::<\/span>out_of_range("The stack is empty!"<\/span>);\n        hazardPointer.store(nullptr);\n        auto<\/span> res =<\/span> oldHead-><\/span>data;\n        if<\/span> ( retireList.isInUse(oldHead) ) retireList.addNode(oldHead);\n        else<\/span> delete<\/span> oldHead;\n        retireList.deleteUnusedNodes();\n        return<\/span> res;\n    }\n};\n\nint<\/span> main<\/span>(){\n\n    LockFreeStack<<\/span>int<\/span>><\/span> lockFreeStack;\n    \n    auto<\/span> fut =<\/span> std::<\/span>async([&<\/span>lockFreeStack]{ lockFreeStack.push(2011<\/span>); });\n    auto<\/span> fut1 =<\/span> std::<\/span>async([&<\/span>lockFreeStack]{ lockFreeStack.push(2014<\/span>); });\n    auto<\/span> fut2 =<\/span> std::<\/span>async([&<\/span>lockFreeStack]{ lockFreeStack.push(2017<\/span>); });\n    \n    auto<\/span> fut3 =<\/span> std::<\/span>async([&<\/span>lockFreeStack]{ return<\/span> lockFreeStack.topAndPop(); });\n    auto<\/span> fut4 =<\/span> std::<\/span>async([&<\/span>lockFreeStack]{ return<\/span> lockFreeStack.topAndPop(); });\n    auto<\/span> fut5 =<\/span> std::<\/span>async([&<\/span>lockFreeStack]{ return<\/span> lockFreeStack.topAndPop(); });\n    \n    fut.get(), fut1.get(), fut2.get();\n    \n    std::<\/span>cout <<<\/span> fut3.get() <<<\/span> '\\n'<\/span>;\n    std::<\/span>cout <<<\/span> fut4.get() <<<\/span> '\\n'<\/span>;\n    std::<\/span>cout <<<\/span> fut5.get() <<<\/span> '\\n'<\/span>;\n\n}\n<\/pre><\/div>\n\n\n\n
The program runs as expected.<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
What’s Next?  <\/h2>\n\n\n\n
I will analyse the program step by step. <\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Hazard Pointers solve all issues of the previous implementation: A Lock-Free Stack: A Simple Garbage Collector. From one Week to two Weeks You may have already noticed. I will change my blog publishing frequency from one to two weeks in the future. Writing a post using your voice is exceptionally exhausting and time-consuming. Hazard Pointers […]<\/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-10682","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\/10682","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=10682"}],"version-history":[{"count":6,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10682\/revisions"}],"predecessor-version":[{"id":10691,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10682\/revisions\/10691"}],"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=10682"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=10682"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=10682"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}