In this blog, we will talk about lock-free programming and its notorious ABA and Memory Reclamation problems along with a few algorithms for dealing with them.

We will start with a brief introduction of lock-free programming and its core Compare-And-Swap (CAS) mechanism, followed by a naive implementation of lock-free stack illustrating the ABA and Memory Reclamation problems. Then we will explore three approaches: Tagged Pointer, Hazard Pointer and Epoch-Based Reclamation.

What is lock-free

Unlike traditional concurrent data structures and algorithms that use mutexes to protect critical sections, lock-free algorithms do not rely on explicit locks to coordinate access between threads.

However, “lock-free” does not simply mean “we don’t use mutexes.” More precisely, a lock-free algorithm guarantees that, even if some threads are delayed or suspended, some thread will always be able to make progress within a finite number of steps.

One of the fundamental mechanisms used to build lock-free algorithms is Compare-And-Swap (CAS). Its basic form is usually described as:

bool compare_and_swap(memory_location, expected_value, new_value);

The underlying hardware guarantees that the comparison and conditional update happen atomically:

  1. if the value currently stored at memory_location is equal to expected_value, it replaces it with new_value and returns true.

  2. Otherwise, the value at memory_location remains unchanged, the current value is stored back into expected_value, and the operation returns false.

Simple as it looks, CAS unlocks a whole universe of amazing programming techniques.

A Naive Lock-free Stack Implementation

Let’s start with the simplest lock-free data structure - Treiber Stack. Being a Last-In-First-Out data structure, the only across thread synchronization point is the head of the stack. Internally we will use a linked list to simulate the stack.

The interface is as simple as the following: only 2 public APIs push and pop.

template<typename T>
class LockfreeStack {
  public:
    struct Node {
        T value_;
        Node* next_;
        explicit Node(const T& value): value_(value), next_(nullptr) {}
    };
    LockfreeStack(): head_(nullptr) {}
    void push(const T& value);
    std::optional<T> pop(void);

  private:
    std::atomic<Node*> head_ = nullptr;
};

push implementation: it creates a new node and links its .next_ to the old head. Then it attempts to swap the new head to be the stack’s head. It’s done in a CAS loop in case another thread updates the head_ while we are attempting to swap the new node to be the head.

template<typename T>
void LockfreeStack<T>::push(const T& value) {
    Node *new_node = new Node(value);
    Node *old_head = head_.load(std::memory_order_relaxed);
    do {
        new_node->next_ = old_head;
    } while(!head_.compare_exchange_weak(old_head, new_node, std::memory_order_release, std::memory_order_relaxed));
}

pop implementation: It grabs the current head and replace the stack’s head with its next node. Once it’s swapped successfully, It might be tempting to assume that it now has exclusive ownership of the old_head and can safely read and delete it.

template<typename T>
std::optional<T> LockfreeStack<T>::pop(void) {
    Node *old_head = head_.load(std::memory_order_acquire);
    while (old_head) {
        Node *new_head = old_head->next_;
        if (head_.compare_exchange_weak(old_head, new_head, std::memory_order_release, std::memory_order_acquire)) {
            T to_ret = std::move(old_head->value_);
            // 2 subtle problems here

            // ABA: if another thread pops out both old_head and new_head, and re-push in a third node of the same address as old_head
            // the CAS will succeed with the head being `new_head`, an already freed node.

            // Memory Reclamation: cannot really delete old_head here, in case another poping thread still holds a reference to old_head
            // when it access old_head->next_ it is UB use-after-free
            delete old_head;
            return to_ret;
        }
    }
    return std::nullopt;
}

I recalled at first glance, the implementation looked perfect fine to me. However, as the comments point out, there are 2 severe problems in the code: ABA and Memory Reclamation. Let’s use some illurations to walk through.

Assume at some point the stack is as follows:

head: A (address 0x100) -> B (address 0x200) -> C (address 0x300)

ABA example:

Time Thread A Thread B
t1 Enter pop()  
t2 old_head = A (0x100)  
t3 new_head = B (0x200)  
t4   pop A (0x100)
t5   pop B (0x200)
t6   push X (reuse address 0x100)
t7 CAS(expected=0x100, new_value=0x200) succeed  
t8 Now the stack head points to already-freed B (0x200)  

The tricky part is at t6 it’s possible for Thread B to allocate and push a new node X at the same address 0x100. Once Thread A resumes, its CAS believes the head is unchanged and successully swap the already-freed B to be the stack head, which corrupts the full data structure.

Memory Reclamation example:

Using a similar sequence of events, we could also identify the memory reclamation problem.

Time Thread A Thread B
t1 Enter pop()  
t2 old_head = A (0x100)  
t3   pop A (0x100)
t4 new_head = B (0x200) (access old_head->next_)  

At t4 it’s invalid to access old_head->next_ since in t3 Thread B have popped and deallocated the node.

Tagged Pointer

The first approach we will look at is Tagged Pointer approach, which only solves the ABA problem but not memory reclamation problem.

Recall the essence of why ABA program occurs is, the CAS only compares the current value of head_ with the expected value we previously observed. With a plain Node*, that value is just the node’s address. However that alone doesn’t guarantee head_’s content has not changed during the course of parallel operations on our stack. Modern memory allocator is free to re-allocate a recently-deallocated memory chunk again.

Built along this insight, Tagged Pointer approach associates each Node * with a version number, making the combined (Node*, version) pair 16 bytes. The CAS now compares and updates the entire (Node*, version) pair atomically. So that, in our ABA example even if thread B newly allocated head X reuses the old A’s address 0x100, it will have a different version number to fail the CAS in thread A.

Implementation-wise we change the declaration to be as follows:

    struct alignas(16) TaggedPointer {
      Node *node_;
      int64_t tag_;
      explicit TaggedPointer(Node *node, int64_t tag = 0): node_(node), tag_(tag) {}
    };

  private:
    std::atomic<TaggedPointer> head_ = nullptr;

In both push and pop, the CAS operations are conducted on the 16 bytes address + tag atomically. And push() will increment the tag versioning for the new head.

template<typename T>
void LockfreeStack<T>::push(const T& value) {
    Node *new_node = new Node(value);
    TaggedPointer old_head = head_.load(std::memory_order_relaxed);
    do {
        new_node->next_ = old_head.node_;
    } while(!head_.compare_exchange_weak(old_head, TaggedPointer(new_node, old_head.tag_+1), std::memory_order_release, std::memory_order_relaxed));
}

template<typename T>
std::optional<T> LockfreeStack<T>::pop(void) {
    TaggedPointer old_head = head_.load(std::memory_order_acquire);
    while (old_head.node_) {
        Node *next_node = old_head.node_->next_;
        if (head_.compare_exchange_weak(old_head, TaggedPointer(next_node, old_head.tag_+1), std::memory_order_release, std::memory_order_acquire)) {
            T to_ret = std::move(old_head.node_->value_);
            // still cannot delete old_head here in case other thread is holding a reference to it
            return to_ret;
        }
    }
    return std::nullopt;
}

On x86-64 systems that support CMPXCHG16B, GCC can implement this 128-bit CAS using the hardware lock cmpxchg16b instruction. With GCC, -mcx16 enables use of the instruction where supported. libatomic.so will eventually dispatch the 128-bit CAS to the right underlying instructions.

$ objdump -d build/lockfree_stack_tagged_pointer
...
00000000000175f0 <_ZN13LockfreeStackIlE4pushERKlm>:
...
   1765c:	e8 cf ba fe ff       	call   3130 <__atomic_compare_exchange_16@plt>

$ objdump -d /lib/x86_64-linux-gnu/libatomic.so.1 | grep cmpxchg16b
...
4205: f0 48 0f c7 0f    lock cmpxchg16b (%rdi)

With a sufficiently large version counter (int64_t), the Tagged Pointer approach prevents the classic ABA problem by making a recycled address distinguishable from its previous incarnation. However, as the comment points out, we still cannot safely free the old_head in the pop() function in case another thread is still holding a reference to it.

Hazard Pointer

The second approach is Hazard Pointer approach, which addresses both the ABA problem and the Memory Reclamation problem. On a high level, this approach makes the explicit communications between threads on “I am about to access/accessing this Node now, please don’t deallocate it” and defer the deallocation until no thread has the node protected by a hazard pointer.

Data structure-wise, each thread is equipped with a thread-local storage for the nodes that’s retired but cannot immediately deallocate. And retire_node will try to deallocate nodes periodically.

  private:
    void retire_node(Node* node) {
      retired_nodes_.push_back(node);
      if (retired_nodes_.size() >= kMaxThreads) {
        std::vector<Node*> new_retired_nodes;
        new_retired_nodes.reserve(kMaxThreads);
        for (Node* node: retired_nodes_) {
          bool can_delete = true;
          for (size_t i = 0; i < kMaxThreads; ++i) {
            if (hazard_pointers_[i].ptr_.load(std::memory_order_seq_cst) == node) {
              can_delete = false;
              break;
            }
          }
          if (can_delete) {
            delete node;
          } else {
            new_retired_nodes.push_back(node);
          }
        }
        retired_nodes_.swap(new_retired_nodes);
      }
    }

    std::atomic<Node*> head_ = nullptr;
    struct alignas(kCacheLineSize) HazardPointer { std::atomic<Node*> ptr_{nullptr};} hazard_pointers_[kMaxThreads];
    static thread_local std::vector<Node*> retired_nodes_;

push() remains unchanged and the pop() changes to

template<typename T>
std::optional<T> LockfreeStack<T>::pop() {
    size_t thread_id = get_thread_id();
    Node *old_head;

    while (true) {
        old_head = head_.load(std::memory_order_acquire);
        if (!old_head) {
            return std::nullopt;
        }
        hazard_pointers_[thread_id].ptr_.store(old_head, std::memory_order_seq_cst);
        if (old_head != head_.load(std::memory_order_seq_cst)) {
            // ensure between we load the head and publish the hazard pointer, the head has not changed
            continue;
        }

        Node *next_node = old_head->next_;
        // important to use seq_cst here for the success publish case
        // to let the unlink participate in the global ordering of
        // hazard pointer publication and re-verify 
        if (head_.compare_exchange_weak(old_head, next_node, std::memory_order_seq_cst, std::memory_order_acquire)) {
            T to_ret = std::move(old_head->value_);
            hazard_pointers_[thread_id].ptr_.store(nullptr, std::memory_order_seq_cst);
            retire_node(old_head);
            return to_ret;
        }
        // don't bother to clean up the hazard pointer here since we will overwrite it in the next iteration anyway
    }
}

One point worth highlighting is there exists a dangerous window in pop between

  • a thread load head via old_head = head_.load(std::memory_order_acquire);
  • subsequently publish its hazard pointer via hazard_pointers_[thread_id].ptr_.store(old_head, std::memory_order_seq_cst);.

That’s why the validation step exists to ensure no other thread updated the head in the middle of these 2 operations.

For simplicity, this implementation uses std::memory_order_seq_cst for the hazard-pointer publication,validation, unlink CAS, and reclamation scan. This gives all participating operations a single global ordering. This makes it easier to reason about the critical ordering between hazard pointer publication, head validation, node unlinking, and reclamation. More optimized Hazard Pointer implementations can use weaker memory orders, but the ordering requirements are considerably more subtle.

Epoch-Based Reclamation

In Epoch-Based Reclamation, each participating thread announces the epoch in which it is currently operating. A retired node is associated with the epoch in which it was removed, and reclamation is deferred until no active thread can still be operating in that epoch or an earlier one. I tend to think of EBR as a coarser-grained form of Hazard Pointer.

Concretely, we design such a data structure:

  private:
    class EpochManager {
        friend class LockfreeStack<T>;
        struct Guard {
            Guard(EpochManager& manager): manager_(manager) {
                size_t thread_id = get_thread_id();
                while (true) {
                    epoch_ = manager_.global_epoch_.load(std::memory_order_seq_cst);
                    manager_.thread_epochs_[thread_id_].epoch_.store(epoch_, std::memory_order_seq_cst);
                    // validation
                    if (epoch_ == manager_.global_epoch_.load(std::memory_order_seq_cst)) {
                        break;
                    }
                }
            }

            ~Guard() noexcept {
                manager_.thread_epochs_[get_thread_id();].epoch_.store(UINT64_MAX, std::memory_order_seq_cst);
            }
            EpochManager& manager_;
            uint64_t epoch_;
        };

        // method   
        void retire_node(Node* node) {
            retired_nodes_.push_back({global_epoch_.load(std::memory_order_seq_cst), node});
            if (retired_nodes_.size() >= kMaxThreads) {
                // find the current global epoch and advance it
                global_epoch_.fetch_add(1, std::memory_order_seq_cst);
                // find min_epoch across threads
                uint64_t min_epoch = UINT64_MAX;
                for (size_t i = 0; i < kMaxThreads; ++i) {
                    uint64_t thread_epoch = thread_epochs_[i].epoch_.load(std::memory_order_seq_cst);
                    if (thread_epoch < min_epoch) {
                        min_epoch = thread_epoch;
                    }
                }
                // retire any old epoch nodes
                std::erase_if(retired_nodes_, [min_epoch](const auto& p) {
                    if (p.first < min_epoch) {
                        delete p.second;
                        return true;
                    }
                    return false;
                });
            }
        }

        // data
        struct alignas(64) ThreadEpoch {
            std::atomic<uint64_t> epoch_{UINT64_MAX};
        } thread_epochs_[kMaxThreads];
        std::atomic<uint64_t> global_epoch_{2};
        thread_local static std::vector<std::pair<uint64_t, Node*>> retired_nodes_;
    } epoch_manager_;

Notice we use a similar publish-and-verify approach in Guard when publishing epoch number, the same approach as we did in Hazard Pointer publication.

To enable and use Epoch-Based Reclamation, we just need to initiate a guard at the beginning of pop to have it publish the epoch number for this thread and its destructor to claw back the epoch number.

template<typename T>
std::optional<T> LockfreeStack<T>::pop(size_t thread_id) {
    typename LockfreeStack<T>::EpochManager::Guard guard(epoch_manager_);
    ... // the rest code as usual
}

All the sample codes are available here for further reference.

Reference