A Lock-Free Stack: A Simple Garbage Collector

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 a to-be-deleted list and delete the nodes on this list if no more than one topAndPush call is active. There is only one challenge left: How can I be sure that not more than one topAndPush call is active? I use an atomic counter that is incremented at the start of topAndPush and decremented at its end. The counter is zero or one if no or one topAndPush call is active.

The following program implements the presented strategy. I use the lockFreeStackWithLeaks.cpp from the article “A Lock-Free Stack: A Complete Implementation” as the starting point.

// lockFreeStackWithGarbageCollection.cpp

#include <atomic>
#include <future>
#include <iostream>
#include <stdexcept>
#include <thread>

template<typename T>
class LockFreeStack {
 private:
    struct Node {
        T data;
        Node* next;
        Node(T d): data(d), next(nullptr){ }
    };

    std::atomic<Node*> head{nullptr};
    std::atomic<int> topAndPopCounter{};                                            // 1
    std::atomic<Node*> toBeDeletedNodes{nullptr};                                   // 2

    void tryToDelete(Node* oldHead) {                                              // 3
        if (topAndPopCounter  == 1) {                                              // 6
            Node* copyOfToBeDeletedNodes = toBeDeletedNodes.exchange(nullptr);     // 8
            if (topAndPopCounter == 1) deleteAllNodes(copyOfToBeDeletedNodes);     // 9
            else addNodeToBeDeletedNodes(copyOfToBeDeletedNodes); 
            delete oldHead;
        }
        else addNodeToBeDeletedNodes(oldHead);                                     // 7
    }

    void addNodeToBeDeletedNodes(Node* oldHead) { 
        oldHead->next = toBeDeletedNodes;
        while( !toBeDeletedNodes.compare_exchange_strong(oldHead->next, oldHead) ); // 10
    }

    void deleteAllNodes(Node* currentNode) {                                      // 4
        while (currentNode) {
            Node* nextNode = currentNode->next;
            delete currentNode;
            currentNode = nextNode;
        }
     }

 public:
    LockFreeStack() = default;
    LockFreeStack(const LockFreeStack&) = delete;
    LockFreeStack& operator= (const LockFreeStack&) = delete;
   
    void push(T val) {
        Node* const newNode = new Node(val); 
        newNode->next = head.load();
        while( !head.compare_exchange_strong(newNode->next, newNode) );
    }

    T topAndPop() {
        ++topAndPopCounter;
        Node* oldHead = head.load();
        while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) {
            if ( !oldHead ) throw std::out_of_range("The stack is empty!");
        }
        auto topElement = oldHead->data;
        tryToDelete(oldHead);                                                   // 5
        --topAndPopCounter;
        return topElement;
    }
};
   
int main(){

    LockFreeStack<int> lockFreeStack;
    
    auto fut = std::async([&lockFreeStack]{ lockFreeStack.push(2011); });
    auto fut1 = std::async([&lockFreeStack]{ lockFreeStack.push(2014); });
    auto fut2 = std::async([&lockFreeStack]{ lockFreeStack.push(2017); });
    
    auto fut3 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
    auto fut4 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
    auto fut5 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
    
    fut.get(), fut1.get(), fut2.get();
    
    std::cout << fut3.get() << '\n';
    std::cout << fut4.get() << '\n';
    std::cout << fut5.get() << '\n';

}

The lock-free stack has two new attributes and three new member functions. The atomic counter
topAndPopCounter counts (line 1) the number of active topAndPop calls, and the atomic pointer toBeDeletedNodes (line 2) is a pointer to the list of the to-be-deleted nodes. Additionally, the member function tryToDelete (line 3) tries to delete removed nodes. The member function addNodeToBeDeletedNodes adds a node to the to-be-deleted list, and the member function deleteAllNodes (line 4) deletes all nodes.

Let’s analyze the member function topAndPop. At the beginning and the end of topAndPop , topAndPopCounter is incremented and decremented. oldHead is removed from the stack and can, therefore, eventually be deleted with the call tryToDelete (line 5). The member function tryToDelete first checks if one or more topAndPop calls are active. If one topAndPop call is active (line 6), oldHead is deleted. If not, oldHead is added to the to-be-deleted list (line 7). I assume that only one topAndPop call is active. In this case, I create a local pointer copyOfToBeDeletedNodes to the to-be-deleted nodes and set the toBeDeletedNodes pointer to a nullptr (line 8). Before I delete the nodes, I check that no additional topAndPop call is active in the meantime. If the current execution topAndPop is still the only one, I use the local pointer copyOfToBeDeletedNodes to delete the list of all to-be-deleted nodes (line 9). If another topAndPop call interleaved, I use the local pointer copyOfToBeDeletedNodes to update toBeDeletedNodes pointer.

Both helper member functions addNodeToBeDeletedNodes and deleteAllNodes iterate through the list. deleteAllNodes is only invoked if one topAndPop call is active. Consequentially, no synchronization is necessary. This observation does not hold for the member function addNodeToBeDeletedNodes (lines 9 and 7). It must be synchronized because more than one topAndPop call can be active. The while loop makes the oldHead the first node in the to-be-deleted nodes and uses a compare_exchange_strong to deal with the fact that topAndPop calls can interleave. Interleaving topAndPop calls cause that oldHead->next != toBeDeletedNodes (line 10) and oldHead->next has to be updated to the toBeDeletedNodes.

So far, this lock-free stack implementation works as expected but has a few flaws. When many
topAndPop calls interleave. it may happen that the counter topAndPopCounter 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.

What´s Next?

Thanks to RCU and Hazard Pointers, these issues can be solved in C++26.

Modernes C++ Mentoring

"Fundamentals for C++ Professionals" (open)

"Design Patterns and Architectural Patterns with C++" (open)

"C++20: Get the Details" (open)

"Concurrency with Modern C++" (open)

"Embedded Programming with Modern C++": January 2025

"Generic Programming (Templates) with C++": February 2025

"Clean Code: Best Practices for Modern C++": May 2025

Do you want to stay informed: Subscribe.

Post Views: 388

Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Stephen Kelley, Kyle Dean, Tusar Palauri, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, Marco Parri Empoli, Philipp Lenk, Charles-Jianye Chen, Keith Jeffery, Matt Godbolt, Honey Sukesan, bruce_lee_wayne, and Silviu Ardelean.

Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.

My special thanks to Embarcadero
My special thanks to PVS-Studio
My special thanks to Tipi.build
My special thanks to Take Up Code
My special thanks to SHAVEDYAKS