{"id":10666,"date":"2025-02-24T11:58:47","date_gmt":"2025-02-24T11:58:47","guid":{"rendered":"https:\/\/www.modernescpp.com\/?p=10666"},"modified":"2025-07-03T14:36:46","modified_gmt":"2025-07-03T14:36:46","slug":"a-lock-free-stack-a-simple-garbage-collector","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/a-lock-free-stack-a-simple-garbage-collector\/","title":{"rendered":"A Lock-Free Stack: A Simple Garbage Collector"},"content":{"rendered":"\n

My next lock-free stack includes a simple garbage collector.<\/p>\n\n\n\n

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

I discussed the concurrent execution of more than one topAndPush <\/code>call is a Race Condition. I can safely delete a node if not more than one topAndPush <\/code>call is executing concurrently. This observation is crucial for solving this memory leak issue: I store removed nodes on a to-be-deleted list and delete the nodes on this list if no more than one topAndPush <\/code>call is active. There is only one challenge left: How can I be sure that not more than one topAndPush <\/code>call is active? I use an atomic counter that is incremented at the start of topAndPush <\/code>and decremented at its end. The counter is zero or one if no or one topAndPush <\/code>call is active.<\/p>\n\n\n\n


The following program implements the presented strategy. I use the lockFreeStackWithLeaks.cpp <\/code>from the article “A Lock-Free Stack: A Complete Implementation<\/a>” as the starting point.<\/p>\n\n\n\n

\/\/ lockFreeStackWithGarbageCollection.cpp<\/span>\n\n#include <atomic><\/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>\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\n    std::<\/span>atomic<<\/span>Node*><\/span> head{nullptr};\n    std::<\/span>atomic<<\/span>int<\/span>><\/span> topAndPopCounter{};                                            \/\/ 1<\/span>\n    std::<\/span>atomic<<\/span>Node*><\/span> toBeDeletedNodes{nullptr};                                   \/\/ 2<\/span>\n\n    void<\/span> tryToDelete<\/span>(Node*<\/span> oldHead) {                                              \/\/ 3<\/span>\n        if<\/span> (topAndPopCounter  ==<\/span> 1<\/span>) {                                              \/\/ 6<\/span>\n            Node*<\/span> copyOfToBeDeletedNodes =<\/span> toBeDeletedNodes.exchange(nullptr);     \/\/ 8<\/span>\n            if<\/span> (topAndPopCounter ==<\/span> 1<\/span>) deleteAllNodes(copyOfToBeDeletedNodes);     \/\/ 9<\/span>\n            else<\/span> addNodeToBeDeletedNodes(copyOfToBeDeletedNodes); \n            delete<\/span> oldHead;\n        }\n        else<\/span> addNodeToBeDeletedNodes(oldHead);                                     \/\/ 7<\/span>\n    }\n\n    void<\/span> addNodeToBeDeletedNodes<\/span>(Node*<\/span> oldHead) { \n        oldHead-><\/span>next =<\/span> toBeDeletedNodes;\n        while<\/span>( !<\/span>toBeDeletedNodes.compare_exchange_strong(oldHead-><\/span>next, oldHead) ); \/\/ 10<\/span>\n    }\n\n    void<\/span> deleteAllNodes<\/span>(Node*<\/span> currentNode) {                                      \/\/ 4<\/span>\n        while<\/span> (currentNode) {\n            Node*<\/span> nextNode =<\/span> currentNode-><\/span>next;\n            delete<\/span> currentNode;\n            currentNode =<\/span> nextNode;\n        }\n     }\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        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        ++<\/span>topAndPopCounter;\n        Node*<\/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        auto<\/span> topElement =<\/span> oldHead-><\/span>data;\n        tryToDelete(oldHead);                                                   \/\/ 5<\/span>\n        --<\/span>topAndPopCounter;\n        return<\/span> topElement;\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 lock-free stack has two new attributes and three new member functions. The atomic counter
topAndPopCounter counts<\/code> (line 1) the number of active topAndPop <\/code>calls, and the atomic pointer toBeDeletedNodes <\/code>(line 2) is a pointer to the list of the to-be-deleted nodes. Additionally, the member function tryToDelete <\/code>(line 3) tries to delete removed nodes. The member function addNodeToBeDeletedNodes <\/code>adds a node to the to-be-deleted list, and the member function deleteAllNodes <\/code>(line 4) deletes all nodes. <\/p>\n\n\n\n
Let\u2019s analyze the member function topAndPop<\/code>. At the beginning and the end of topAndPop <\/code>, topAndPopCounter <\/code>is incremented and decremented. oldHead <\/code>is removed from the stack and can, therefore, eventually be deleted with the call tryToDelete <\/code>(line 5). The member function tryToDelete <\/code>first checks if one or more topAndPop <\/code>calls are active. If one topAndPop <\/code>call is active (line 6), oldHead <\/code>is deleted. If not, oldHead <\/code>is added to the to-be-deleted list (line 7). I assume that only one topAndPop <\/code>call is active. In this case, I create a local pointer copyOfToBeDeletedNodes <\/code>to the to-be-deleted nodes and set the toBeDeletedNodes <\/code>pointer to a nullptr <\/code>(line 8). Before I delete the nodes, I check that no additional topAndPop <\/code>call is active in the meantime. If the current execution topAndPop <\/code>is still the only one, I use the local pointer copyOfToBeDeletedNodes <\/code>to delete the list of all to-be-deleted nodes (line 9). If another topAndPop <\/code>call interleaved, I use the local pointer copyOfToBeDeletedNodes <\/code>to update toBeDeletedNodes <\/code>pointer.<\/p>\n\n\n\n

Both helper member functions addNodeToBeDeletedNodes <\/code>and deleteAllNodes <\/code>iterate through the list. deleteAllNodes <\/code>is only invoked if one topAndPop <\/code>call is active. Consequentially, no synchronization is necessary. This observation does not hold for the member function addNodeToBeDeletedNodes <\/code>(lines 9 and 7). It must be synchronized because more than one topAndPop <\/code>call can be active. The while loop makes the oldHead <\/code>the first node in the to-be-deleted nodes and uses a compare_exchange_strong<\/code> to deal with the fact that topAndPop calls can interleave. Interleaving topAndPop calls cause that oldHead->next !=<\/code> toBeDeletedNodes <\/code>(line 10) and oldHead->next <\/code>has to be updated to the toBeDeletedNodes<\/code>.<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
So far, this lock-free stack implementation works as expected but has a few flaws. When many
topAndPop <\/code>calls interleave. it may happen that the counter topAndPopCounter <\/code>never becomes one. It means that the nodes in the to-be-deleted lists of nodes are not deleted, and we have a memory leak. Additionally, the number of the to-be-deleted nodes may become a resource issue.<\/p>\n\n\n\n
What\u00b4s Next?<\/h2>\n\n\n\n
Thanks to RCU and Hazard Pointers, these issues can be solved in C++26.<\/p>\n\n\n\n
<\/p>\n\n\n\n
<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
My next lock-free stack includes a simple garbage collector. I discussed the concurrent execution of more than one topAndPush call is a Race Condition. I can safely delete a node if not more than one topAndPush call is executing concurrently. This observation is crucial for solving this memory leak issue: I store removed nodes on […]<\/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-10666","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\/10666","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=10666"}],"version-history":[{"count":10,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10666\/revisions"}],"predecessor-version":[{"id":10678,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10666\/revisions\/10678"}],"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=10666"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=10666"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=10666"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}