Recently, I studied the ABA problem in lock-free stacks, and I would like to share my insights.Lock-free data structures are data structures implemented using CAS (Compare and Swap). In contrast, traditional data structures use locks.On CPUs with multiple hardware threads, lock-free data structures improve performance as the number of threads increases; whereas, lock-based data structures experience performance degradation with an increase in thread count.Lock-free data structures can achieve true parallelism, while lock-based structures are effectively serial due to lock contention.
CAS
In C++, the CAS (Compare-And-Swap) operation is primarily implemented through the member functions compare_exchange_weak and compare_exchange_strong of the std::atomic class template. Both functions can atomically perform the comparison and swap operation.
bool compare_exchange_weak(T& expected, T desired, std::memory_order success, std::memory_order failure) noexcept;bool compare_exchange_strong(T& expected, T desired, std::memory_order success, std::memory_order failure) noexcept;Parameter descriptions:
expected: A reference parameter that receives the expected value; if CAS fails, it will be updated to the current value.
desired: The new value that is desired to be set.
success: The memory order when CAS is successful.
failure: The memory order when CAS fails.
The comparison between these two functions is as follows:
| Feature | compare_exchange_weak | compare_exchange_strong |
|---|---|---|
| False failure | May occur | Will not occur |
| Performance | Higher | Lower |
| Usage scenario | Within a loop | Single attempt |
| Code pattern | <span>while (!cas_weak(...))</span> |
<span>if (cas_strong(...))</span> |
Consider the following code, assuming there are two threads. Scenario 1: Before thread 1 executes head.compare_exchange_weak, thread 2 has not changed the value of head. At this point, thread 1 will atomically compare head and old_head, find them equal, and assign old_head->next to head. Scenario 2: Before thread 1 executes head.compare_exchange_weak, thread 2 has changed the value of head. In this case, thread 1 will atomically compare head and old_head, find them unequal, and assign head to old_head.
#include <atomic>#include <memory>#include <iostream>struct Node { std::shared_ptr<int> data; // Using shared_ptr to manage data Node* next; Node(const int& value) : data(std::make_shared<int>(value)), next(nullptr) {}};int main() { std::atomic<Node*> head; Node* old_head = head.load(std::memory_order_relaxed); Node* new_head = nullptr; do { if (!old_head) break; // Safely read the next pointer within the loop } while (!head.compare_exchange_weak(old_head, old_head->next, std::memory_order_acquire, std::memory_order_relaxed)); return 0;}It is important to note that only the compare_exchange_weak function is atomic, while the operations of assigning values to the function parameters are not. This point is quite significant for understanding the ABA problem; one cannot consider the reading of old_head, reading of old_head->next, and the compare_exchange_weak operation as a single atomic operation. For more details, please refer to the assembly code below.
Lock-Free StackIn the following sections, I will use the lock-free stack as an example to introduce the ABA problem, so let’s first look at the implementation code.
#include <atomic>#include <memory>#include <iostream>#include <thread>#include <vector>#include <random>// Lock-free stack template classtemplate<typename T>class LockFreeStack {private: // Stack node structure struct Node { std::shared_ptr<T> data; // Using shared_ptr to manage data Node* next; Node(const T& value) : data(std::make_shared<T>(value)), next(nullptr) {} }; // Head node pointer std::atomic<Node*> head;public: LockFreeStack() : head(nullptr) {} // Disable copy constructor and assignment LockFreeStack(const LockFreeStack&) = delete; LockFreeStack& operator=(const LockFreeStack&) = delete; ~LockFreeStack() { // Clear the stack during destruction while (pop()); } // Push operation void push(const T& value) { Node* new_node = new Node(value); new_node->next = head.load(std::memory_order_relaxed); // Use CAS operation to update the head node while (!head.compare_exchange_weak(new_node->next, new_node, std::memory_order_release, std::memory_order_relaxed)); } // Pop operation, returns the data's shared_ptr std::shared_ptr<T> pop() { Node* old_head = head.load(std::memory_order_relaxed); // Use CAS operation to update the head node while (old_head && !head.compare_exchange_weak(old_head, old_head->next, std::memory_order_acquire, std::memory_order_relaxed)); if (!old_head) { return std::shared_ptr<T>(); // Stack is empty, return null pointer } std::shared_ptr<T> res = old_head->data; // Get data delete old_head; // Delete node return res; } // Check if the stack is empty bool empty() const { return head.load(std::memory_order_acquire) == nullptr; } // Get the top element (without popping) std::shared_ptr<T> top() const { Node* current_head = head.load(std::memory_order_acquire); if (!current_head) { return std::shared_ptr<T>(); } return current_head->data; }};// Basic functionality testvoid basic_function_test() { std::cout << "=== Basic Function Test ===\n"; LockFreeStack<int> stack; // Test empty stack std::cout << "Empty stack test: " << (stack.empty() ? "Passed" : "Failed") << std::endl; // Test push and pop stack.push(1); stack.push(2); stack.push(3); auto top_val = stack.top(); if (top_val && *top_val == 3) { std::cout << "Top test: Passed" << std::endl; } else { std::cout << "Top test: Failed" << std::endl; } auto val3 = stack.pop(); auto val2 = stack.pop(); auto val1 = stack.pop(); auto val_empty = stack.pop(); if (val3 && *val3 == 3 && val2 && *val2 == 2 && val1 && *val1 == 1 && !val_empty) { std::cout << "Push/Pop test: Passed" << std::endl; } else { std::cout << "Push/Pop test: Failed" << std::endl; } std::cout << "Empty after pops: " << (stack.empty() ? "Yes" : "No") << std::endl;}int main() { std::cout << "Lock-Free Stack Implementation Test\n"; std::cout << "===================================\n"; // Run basic functionality test basic_function_test(); return 0;}ABA Problem
Consider the following diagram, assuming the lock-free stack initially stores 3->2->1. Thread 1 loads old_head and old_head->next but has not yet executed CAS. If, from this moment until thread 1 executes CAS, thread 2 performs two pop operations and then executes a push, and the address newly allocated by the operating system happens to be 0x3000, and thread 2 ends. Next, when thread 1 starts CAS, it finds that the value of head is equal to old_head, and assigns 0x2000 to head, which has already been popped and deleted by thread 2. This can lead to undefined behavior.
