{"id":10619,"date":"2025-02-10T15:01:19","date_gmt":"2025-02-10T15:01:19","guid":{"rendered":"https:\/\/www.modernescpp.com\/?p=10619"},"modified":"2025-07-03T14:34:20","modified_gmt":"2025-07-03T14:34:20","slug":"a-lock-free-stack-a-complete-implementation","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/a-lock-free-stack-a-complete-implementation\/","title":{"rendered":"A Lock-Free Stack: A Complete Implementation"},"content":{"rendered":"\n

My last lock-free stack implementation was incomplete. It only supported push operations. Let’s change this. <\/p>\n\n\n\n

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

The following paragraph about sequential consistency is optional. You can easily ignore it.<\/p>\n\n\n\n

Sequential Consistency <\/h2>\n\n\n\n

In my examples, I use the default memory ordering: sequential consistency<\/a>. The reason is simple. Sequential consistency provides the strongest guarantees of all memory ordering and is, therefore, easier to use than the other memory orders. Sequential consistency is an ideal starting point when designing lock-free data structures. In further optimization steps, you can weaken the memory ordering and apply acquire-release semantics<\/a> or relaxed semantics<\/a>.<\/p>\n\n\n\n


Depending on the architecture, weakening the memory ordering may not pay off. For example, the
x86 memory model is one of the strongest memory models of all modern architectures. As a result,
breaking the sequential consistency and applying a weaker memory ordering might not give the
performance improvements you hoped for. On the contrary, ARMv8, PowerPC, Itanium, and, in
particular, DEC alpha may pay off when breaking the sequential consistency.<\/p>\n\n\n\n

The simplified stack version from the last article has two issues. First, it does not have a pull <\/code> operation, and second, it releases no memory.<\/p>\n\n\n\n

A Complete Implementation<\/h2>\n\n\n\n

Typically, a stack supports the member functions push<\/code>, pop<\/code>, and top<\/code>. Implementing the pop <\/code>and top<\/code> member functions thread-safe, does not guarantee that the invocation of top <\/code>followed by pop <\/code>is threadsafe. It may happen that one thread t1<\/code> called stack.top()<\/code> and is interleaved by another thread t2<\/code> that called stack.top() <\/code>and then stack.pop()<\/code>. Now, the final pop <\/code>call is based on the wrong stack size.<\/p>\n\n\n\n

No Memory Reclamation<\/h3>\n\n\n\n

Consequentially, the following implementation combines the two member functions top <\/code>and pop <\/code>into one: topAndPop<\/code>.<\/p>\n\n\n\n

\/\/ lockFreeStackWithLeaks.cpp<\/span>\n\n#include <atomic><\/span>\n#include <future><\/span>\n#include <iostream><\/span>\n#include <stdexcept><\/span>\n\ntemplate<\/span><<\/span>typename<\/span> T><\/span>\nclass<\/span> LockFreeStack<\/span> {\n private:<\/span>\n    struct<\/span> Node {\n        T data;\n        Node*<\/span> next;\n        Node(T d):<\/span> data(d), next(nullptr){ }\n    };\n    std::<\/span>atomic<<\/span>Node*><\/span> head;\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        Node*<\/span> const<\/span> newNode =<\/span> new<\/span> Node(val);\n        newNode-><\/span>next =<\/span> head.load();\n        while<\/span>( !<\/span>head.compare_exchange_strong(newNode-><\/span>next, newNode) );\n    }\n\n    T topAndPop<\/span>() {\n        Node*<\/span> oldHead =<\/span> head.load();                                                 \/\/ 1<\/span>\n        while<\/span>( oldHead &&<\/span> !<\/span>head.compare_exchange_strong(oldHead, oldHead-><\/span>next) ) {  \/\/ 2<\/span>\n            if<\/span> ( !<\/span>oldHead ) throw<\/span> std::<\/span>out_of_range("The stack is empty!"<\/span>);          \/\/ 3<\/span>\n        }\n        return<\/span> oldHead-><\/span>data;                                                        \/\/ 4<\/span>\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();                            \/\/ 5  <\/span>\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 member function topAndPop <\/code>returns the top element of the stack. It reads the head element of the stack (line 1) and makes the next node the new head if oldHead <\/code>is not a nullptr <\/code>(line 2). oldhead <\/code>is a nullptr <\/code>if the stack is empty. I throw an exception if the stack is empty (line 3). Returning a special non-value or returning a std::optional<\/code> is also a valid option. Copying the value has a downside. If the copy constructor of the value throws an exception such as std::bad_alloc<\/code>, the value is lost. Finally, the member functions returns the head element (line 4).
<\/p>\n\n\n\n
The calls fut.get(), fut1.get(), fut2.get() <\/code>(line 5) ensure that the associated promise runs. If you don\u2019t specify the launch policy the promise may run lazily in the caller\u2019s thread. Lazily means that the promise will be executed if and only if the future asks for its result with get <\/code>or wait<\/code>. You can also launch the promise in a separate thread:<\/p>\n\n\n\n
auto<\/span> fut =<\/span> std::<\/span>async(std::<\/span>launch::<\/span>asnyc, [&<\/span>conStack]{ conStack.push(2011<\/span>); });\nauto<\/span> fut1 =<\/span> std::<\/span>async(std::<\/span>launch::<\/span>asnyc, [&<\/span>conStack]{ conStack.push(2014<\/span>); });\nauto<\/span> fut2 =<\/span> std::<\/span>async(std::<\/span>launch::<\/span>asnyc, [&<\/span>conStack]{ conStack.push(2017<\/span>); });\n<\/pre><\/div>\n\n\n\n
Finally, the output of the program:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Although the presented lock-free stack supports push<\/code> and topAndPop<\/code>, it has a serious issue: it leaks memory. You may ask: Why can\u2019t the oldHead <\/code>just be removed after the call head.compare_exchange_strong(oldHead, oldHead->next)<\/code> (line 2) in the member function topAndPop<\/code>? The answer is that another thread may use oldHead<\/code>. Let\u2019s analyze the member functions push <\/code>and topAndPop<\/code>. Concurrent execution of push <\/code>is no issue because the call !head.compare_exchange_strong(newNode->next, newNode)<\/code> atomically updates newNode->next<\/code> to the new head. It is also valid if only one topAndPop <\/code>call happens. The issue arises when more topAndPop <\/code>calls interleave with or without a push<\/code> call. Deleting the oldHead <\/code>while another thread uses it would be disastrous because the deletion of oldHead <\/code>must always happen before or after its update to the new head: oldHead->next<\/code> (line 2).<\/p>\n\n\n\n
What’s Next?<\/h2>\n\n\n\n
Thanks to RCU and Hazard Pointers, I can solve the memory leaks in my next post. <\/p>\n","protected":false},"excerpt":{"rendered":"
My last lock-free stack implementation was incomplete. It only supported push operations. Let’s change this. The following paragraph about sequential consistency is optional. You can easily ignore it. Sequential Consistency In my examples, I use the default memory ordering: sequential consistency. The reason is simple. Sequential consistency provides the strongest guarantees of all memory ordering […]<\/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-10619","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\/10619","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=10619"}],"version-history":[{"count":5,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10619\/revisions"}],"predecessor-version":[{"id":10636,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10619\/revisions\/10636"}],"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=10619"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=10619"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=10619"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}