{"id":10651,"date":"2025-02-17T11:47:15","date_gmt":"2025-02-17T11:47:15","guid":{"rendered":"https:\/\/www.modernescpp.com\/?p=10651"},"modified":"2025-07-03T14:35:42","modified_gmt":"2025-07-03T14:35:42","slug":"a-lock-free-stack-atomic-smart-pointer","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/a-lock-free-stack-atomic-smart-pointer\/","title":{"rendered":"A Lock-Free Stack: Atomic Smart Pointer"},"content":{"rendered":"\n

The easiest way to solve this memory leak issue from the last post is to use a std::shared_ptr<\/code>.<\/p>\n\n\n\n

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

Atomic Smart Pointer<\/h2>\n\n\n\n

There are two ways to apply atomic operations on a std::shared_ptr<\/code>: In C++11, you can use the free atomic functions on std::shared_ptr.<\/code> With C++20, you can use atomic smart pointers.<\/p>\n\n\n\n

C++11<\/h3>\n\n\n\n

Using atomic operations on std::shared_ptr<\/code> is tedious and error-prone. You can easily forget the atomic operations, and all bets are open. The following example shows a lock-free stack based on std::shared_ptr<\/code>.<\/p>\n\n\n\n

\/\/ lockFreeStackWithSharedPtr.cpp<\/span>\n\n#include <atomic><\/span>\n#include <future><\/span>\n#include <iostream><\/span>\n#include <stdexcept><\/span>\n#include <memory><\/span>\n\ntemplate<\/span><<\/span>typename<\/span> T><\/span>\nclass<\/span> LockFreeStack<\/span> {\n public:<\/span>\n    struct<\/span> Node {\n        T data;\n        std::<\/span>shared_ptr<<\/span>Node><\/span> next;\n    };\n    std::<\/span>shared_ptr<<\/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        auto<\/span> newNode =<\/span> std::<\/span>make_shared<<\/span>Node><\/span>();\n        newNode-><\/span>data =<\/span> val;\n        newNode-><\/span>next =<\/span> std::<\/span>atomic_load(&<\/span>head);                                       \/\/ 1<\/span>\n        while<\/span>( !<\/span>std::<\/span>atomic_compare_exchange_strong(&<\/span>head, &<\/span>newNode-><\/span>next, newNode) ); \/\/ 2<\/span>\n    }\n\n    T topAndPop<\/span>() {\n        auto<\/span> oldHead =<\/span> std::<\/span>atomic_load(&<\/span>head);                                       \/\/ 3<\/span>\n        while<\/span>( oldHead &&<\/span> !<\/span>std::<\/span>atomic_compare_exchange_strong(&<\/span>head, &<\/span>oldHead, std::<\/span>atomic_load(&<\/span>oldHead-><\/span>next)) ) {     \/\/ 4<\/span>\n            if<\/span> ( !<\/span>oldHead ) throw<\/span> std::<\/span>out_of_range("The stack is empty!"<\/span>);\n        }\n        return<\/span> oldHead-><\/span>data;\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
This lock-free stack implementation is quite similar to the previous one without memory reclamation. The main difference is that the nodes are of type std::shared_ptr<\/code>. All operations std::shared_ptr <\/code>are done atomically by using the free atomic operations std::load<\/code> (lines 1 and 4), and std::atomic_compare_exchange_strong<\/code> (lines 2 and 3). The free atomics operations require a pointer. I want to emphasize explicitly, the read operation of the next node in oldHead->next<\/code> (line 4) must be atomic because oldHead->next<\/code> can be used by other threads. <\/p>\n\n\n\n
Finally, here is the output of the program.<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Let\u2019s jump nine years into the future and use C++20.<\/p>\n\n\n\n
C++20
<\/h3>\n\n\n\n
C++20 supports partial specializations of std::atomic<\/code> for std::shared_ptr <\/code>and std::weak_ptr<\/code>. The following implementation puts the nodes of the lock-free stack into a std::atomic<std::shared_ptr<Node><\/code>>.<\/p>\n\n\n\n
\/\/ lockFreeStackWithAtomicSharedPtr.cpp<\/span>\n\n#include <atomic><\/span>\n#include <future><\/span>\n#include <iostream><\/span>\n#include <stdexcept><\/span>\n#include <memory><\/span>\n\ntemplate<\/span><<\/span>typename<\/span> T><\/span>\nclass<\/span> LockFreeStack<\/span> {\n private:<\/span>\n    struct<\/span> Node {\n        T data;\n        std::<\/span>shared_ptr<<\/span>Node><\/span> next;\n    };\n    std::<\/span>atomic<<\/span>std::<\/span>shared_ptr<<\/span>Node>><\/span> head;           \/\/ 1<\/span>\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) {                              \/\/ 2<\/span>\n        auto<\/span> newNode =<\/span> std::<\/span>make_shared<<\/span>Node><\/span>();\n        newNode-><\/span>data =<\/span> val;\n        newNode-><\/span>next =<\/span> head;\n        while<\/span>( !<\/span>head.compare_exchange_strong(newNode-><\/span>next, newNode) );\n    }\n\n    T topAndPop<\/span>() {\n        auto<\/span> oldHead =<\/span> head.load();\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        }\n        return<\/span> oldHead-><\/span>data;\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 main difference between the previous and this implementation is that the Node<\/code> is embedded into a std::atomic<std::shared_ptr<Node><\/code>> (line 1). Consequentially, the member function push <\/code>(line 2) creates a std::shared_ptr<Node><\/code> and the call head.load()<\/code> in the member function topAndPop <\/code>returns a std::atomic<std::shared_ptr<Node><\/code>>.<\/p>\n\n\n\n
Here is the output of the program.<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
std::atomic<std::shared_ptr<\/code>> is not Lock-Free <\/h4>\n\n\n\n
Honestly, I cheated in the previous programs using atomic operations on a std::shared_ptr <\/code>and a std::atomic<\/code>. Those atomic operations on a std::shared_ptr<\/code> are currently not lock-free. Additionally, an implementation of std::atomic<\/code> can use a locking mechanism to support all partial and full specializations of std::atomic<\/code>. <\/p>\n\n\n\n
The call atom.lock_free()<\/code> on a std::atomic<std::shared_ptr<Node><\/code>>  returns false<\/code>.<\/p>\n\n\n\n
 \/\/ atomicSmartPointer.cpp<\/span>\n \n#include <atomic><\/span>\n#include <iostream><\/span>\n#include <memory><\/span>\n\ntemplate<\/span> <<\/span>typename<\/span> T><\/span>\nstruct<\/span> Node {\n    T data;\n    std::<\/span>shared_ptr<<\/span>Node><\/span> next;   \n};\n\nint<\/span> main<\/span>() {    \n\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n    std::<\/span>cout <<<\/span> std::<\/span>boolalpha;\n\n    std::<\/span>atomic<<\/span>std::<\/span>shared_ptr<<\/span>Node<<\/span>int<\/span>>>><\/span> node;\n    std::<\/span>cout <<<\/span> "node.is_lock_free(): "<\/span>  <<<\/span> node.is_lock_free() <<<\/span> '\\n'<\/span>;\n\n    std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n}\n<\/pre><\/div>\n\n\n\n
What’s Next?<\/h2>\n\n\n\n
So, we are back to square one and need to worry about memory management in my next post.<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
The easiest way to solve this memory leak issue from the last post is to use a std::shared_ptr. Atomic Smart Pointer There are two ways to apply atomic operations on a std::shared_ptr: In C++11, you can use the free atomic functions on std::shared_ptr. With C++20, you can use atomic smart pointers. C++11 Using atomic operations […]<\/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,399],"class_list":["post-10651","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c26-blog","tag-hazard-pointers","tag-smart-pointers"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10651","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=10651"}],"version-history":[{"count":10,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10651\/revisions"}],"predecessor-version":[{"id":10663,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10651\/revisions\/10663"}],"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=10651"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=10651"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=10651"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}