A Lock-Free Stack: A Hazard Pointer Implementation Explained II

In my last post, I started to explain a hazard pointer implementation: A Lock-Free Stack: A Hazard Pointer Implementation Explained I. Today, I will continue to explain the implementation.

The Retire List

The retire list has the public member functions isInUse, addNode, and deleteUnusedNodes. Additionally, it has the inner class RetireNode, an atomic member of it, and the private member function addToRetiredNodes.

template <typename T, Node MyNode = MyNode<T>>
class RetireList {

    struct RetiredNode {
        MyNode* node;
        RetiredNode* next;
        RetiredNode(MyNode* p) : node(p), next(nullptr) { }
        ~RetiredNode() {
            delete node;
        }
    };

    std::atomic<RetiredNode*> RetiredNodes;

    void addToRetiredNodes(RetiredNode* retiredNode) {
        retiredNode->next = RetiredNodes.load();
        while (!RetiredNodes.compare_exchange_strong(retiredNode->next, retiredNode));
    }

 public:

    bool isInUse(MyNode* node) {
        for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
            if (HazardPointers<T>[i].pointer.load() == node) return true;
        }
        return false;
    }

    void addNode(MyNode* node) {
        addToRetiredNodes(new RetiredNode(node));
    }

    void deleteUnusedNodes() {
        RetiredNode* current = RetiredNodes.exchange(nullptr);
        while (current) {
            RetiredNode* const next = current->next;
            if (!isInUse(current->node)) delete current;
            else addToRetiredNodes(current);
            current = next;
        }
    }
};

Let’s start with the interface of the type RetireList.

The member function isInUse checks if node is in use. It does its job by traversing the variable template HazardPointers that is parameterized on the type of data the node holds. HazardPointers is a C-array of HazardPointer of length 50. A HazardPointer consists of an atomic thread id and an atomic pointer to a node.

constexpr std::size_t MaxHazardPointers = 50;

template <typename T, Node MyNode = MyNode<T>>
struct HazardPointer {
    std::atomic<std::thread::id> id;
    std::atomic<MyNode*> pointer;
};

template <typename T>
HazardPointer<T> HazardPointers[MaxHazardPointers];

Using an STL container such as std::set as HazardPointers is much more convenient. std::set is already ordered and guarantees constant access time on average but has a big issue: it’s not thread-safe.

The member function addNode takes a node, invokes the private member function addToRetiredNodes, and puts the node into an RetiredNode. RetiredNode is an RAII object and guarantees that the wrapped node is destroyed, releasing its memory. All retired nodes build a singly-linked list.

The member function deleteUnusedNodes traverses the singly-linked list of retired nodes by applying the following pattern:

    void deleteUnusedNodes() {
        RetiredNode* current = RetiredNodes.exchange(nullptr);
        while (current) {
            RetiredNode* const next = current->next;
            if (!isInUse(current->node)) delete current;
            else addToRetiredNodes(current);
            current = next;
        }
    }

It checks the current node, points the next node to current->next and updates the current node with the next node. Finally, the current node is destroyed if not used anymore or added to the retired nodes. The private member function addToRetireNodes adds the retired nodes to the singly-linked list. To perform its job, it loads the RetiredNodes and makes the new node retiredNode to the new head of the singly-linked list. Before retiredNode becoming the new head of the singly-linked list, I have to ensure that it is still the head of the singly-linked list because another thread could kick in and change the head of the singly-linked list in the meantime. Thanks to the while-loop, retiredNode becomes only the new head if retiredNode->next = RetiredNodes.load() holds. If not, retiredNode->next is updated to RetiredNodes.load().

There is only one piece of the puzzle left:

The Hazard Pointer Owner

template <typename T, Node MyNode = MyNode<T>>
class HazardPointerOwner {

    HazardPointer<T>* hazardPointer;

 public:
    HazardPointerOwner(HazardPointerOwner const &) = delete;
    HazardPointerOwner operator=(HazardPointerOwner const &) = delete;

    HazardPointerOwner() : hazardPointer(nullptr) {
        for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
            std::thread::id old_id;
            if (HazardPointers<T>[i].id.compare_exchange_strong(
                                        old_id, std::this_thread::get_id())) {
                hazardPointer = &HazardPointers<T>[i];
                break;
            }
        }
        if (!hazardPointer) {
            throw std::out_of_range("No hazard pointers available!");
        }
    }

    std::atomic<MyNode*>& getPointer() {
        return hazardPointer->pointer;
    }

    ~HazardPointerOwner() {
        hazardPointer->pointer.store(nullptr);
        hazardPointer->id.store(std::thread::id());
    }
};

HazardPointerOwner holds a hazardPointer. This hazardPointer is set in the constructor by traversing all HazardPointers. The compare_exchange_strong call checks in an atomic step if the currently traversed hazard pointer is not set and sets its id to the id of the now executed thread (std::this_thread::get_id()). In the success case, hazardPointer becomes the new hazard pointer returned to the client invoking the member function getPointer. When all of the hazard pointers of HazardPointers are used, the constructor throws a std::out_of_range exception. Finally, HazardPointerOwner‘s destructor sets the hazardPointer to its default state.

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.

What’s Next?

In C++26, we will get hazard pointers. I will write about them in my next post.

Post Views: 1,784

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, Silviu Ardelean, and Seeker.

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