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

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

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

MyNode <\/code>is a class template, parametrized by the type it holds: data. MyNode <\/code>models the concept Node<\/code>.<\/p>\n\n\n\n

template<\/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<\/pre><\/div>\n\n\n\n
Concepts are compile-time predicates. They put semantic constraints on template parameters. The concept Node <\/code>requires member data<\/code> and a pointer next <\/code>that returns a Node<\/code>. The program lockFreeStackHazardPointers.cpp <\/code>types are essentially parametrized on the data <\/code>member and the concept Node. MyNode<\/code> models the concept Node<\/code>. For example, here is the declaration of the LockFreeStack<\/code>:<\/p>\n\n\n\n
template<\/span><<\/span>typename<\/span> T, Node MyNode =<\/span> MyNode<<\/span>T>><\/span>\n\nclass<\/span> LockFreeStack<\/span>;\n<\/pre><\/div>\n\n\n\n
Let me continue my analysis of the program with the lock-free stack.<\/p>\n\n\n\n
template<<\/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<\/pre><\/div>\n\n\n\n
The push <\/code>call is not critical from a concurrency perspective because head <\/code>is updated in an atomic step. Additionally, the compare_exchange_strong <\/code>call guarantees that head <\/code>is always the current head of the stack.<\/p>\n\n\n\n
Due to hazard pointers, the call topAndPop <\/code>becomes more complicated. First, the function getHazardPointer <\/code>references the hazard pointer for the current thread. The call hazardPointer.store(oldHead)<\/code> makes the current thread to the owner of the hazard pointer, and the call hazardPointer.store(nullptr)<\/code>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 ==<\/code> tempNode<\/code>. Both nodes are equal if oldHead <\/code>is still the current head of the lock-free stack. oldHead <\/code>was set and could not be the current head anymore because another thread may be kicked in and already managed oldHead<\/code>. 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 <\/code>and set the head <\/code>to oldHead->next.<\/code> In the end, head <\/code>is the head of the stack. Remember, the member function topAndPop <\/code>should return the value of the head and remove it. Before I use oldHead <\/code>I have to check if oldHead <\/code>is not a null pointer. If oldHead <\/code>is a null pointer, I throw an exception. The rest of the topAndPop <\/code>is straightforward. \u00a0The call retireList.isInUse(oldHead)<\/code> checks if oldHead <\/code>is still in use. Depending on this check, oldHead <\/code>is added to the retire list retireList.addNode<\/code> if it is not yet on the list or deleted. The last call retireList.deleteUnusedNodes<\/code> is the most labor-intensive call in the member function topAndPop<\/code>. The member function retireListe.deleteUnusedNodes<\/code> traverses the entire retire list and deletes all nodes that are not used anymore.<\/p>\n\n\n\n
For performance reasons, the call retireList.deleteUnusedNodes <\/code>should not be executed in each call of topAndPop<\/code>. An improved strategy is to invoke the member function deleteUnusedNodes<\/code> 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.<\/p>\n\n\n\n
Let me continue my explanation with the free function getHazardPointer<\/code>.<\/p>\n\n\n\n
template<\/span> <<\/span>typename<\/span> T, Node MyNode =<\/span> MyNode<<\/span>T>><\/span>\nsttd::<\/span>atomic<<\/span>MyNode*>&<\/span> getHazardPointer() {\n    thread_local static<\/span> HazardPointerOwner<<\/span>T><\/span> hazard;\n    return<\/span> hazard.getPointer();\n}\n<\/pre><\/div>\n\n\n\n
The function getHazardPointer <\/code>references a hazard pointer using the hazard pointer owner hazard. hazard<\/code> 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<\/code>.<\/p>\n\n\n\n
What’s Next?<\/h2>\n\n\n\n
In my next post, I will explain the remaining implementation.<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
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&>; […]<\/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-10705","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\/10705","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=10705"}],"version-history":[{"count":5,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10705\/revisions"}],"predecessor-version":[{"id":10710,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10705\/revisions\/10710"}],"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=10705"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=10705"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=10705"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}