In the previous lesson, we learned that relying on the global allocator for lock-free structures leads to use-after-free segmentation faults and the ABA problem. To solve this, we built `LockFreePool` - a concurrent, ABA-proof memory allocator. In this lesson, we'll build a `LockFreeStack` class on top of these foundations. ### Recommended Reading This lesson is a direct follow-up to the previous, where we created a lock-free object pool. We'll be using that pool in this lesson. Additionally, this lesson pulls together many techniques we covered in the previous chapters. To follow along, being particularly comfortable with the following topics is highly recommended: - Creating an index-based linked list, particularly the logical steps required to push and pop elements at the head - Implementing custom atomic logic using compare-and-swap (CAS) - The challenges of working with lock-free pointers ## The LIFO Contention Problem Throughout this chapter, we have focused on data flow. If we need a LIFO data stream to process reverse-chronological workloads (like an undo history or a global task scheduler), our first instinct is to use the standard library's `std::stack`. To make it safe for multithreading, we wrap it in a `std::mutex`: ```c++ #include #include std::stack TaskStack; std::mutex StackMutex; void AddTask(int TaskID) { std::lock_guard lock(StackMutex); // TaskStack.push(TaskID); } ``` We've documented and tested the performance implications of locks in past lessons, but they're particularly problematic in the context of a stack-based access pattern. A stack restricts all access to a single physical point: the top of the collection - usually called the `Head`. If we have 16 threads fighting to pull tasks from a global stack, they are all contending for this same memory address. To alleviate this, we can use a lock-free stack implementation. We will build a **Treiber stack** - a common design for a lock free stack. It uses a singly-linked list. In our implementation, the nodes of our list will be allocated in our `LockFreePool`, so we'll use index-based linking. ## Treiber Stacks Let's establish the foundation of our `LockFreeStack`. We will use our `LockFreePool` to manage the physical memory, allowing us to focus entirely on the stack logic. Below, we define a nested `Node` struct. The stack needs to define its own `Next` pointer to manage the active LIFO sequence. Our underlying pool is completely oblivious to this - it just sees `Node` as an opaque payload to store inside its own internal objects, which we called `Slot` in the previous lesson. ```c++ #pragma once #include #include #include #include #include template class LockFreeStack { private: static_assert( std::is_nothrow_copy_assignable_v, "Type T must not throw to guarantee exception safety" ); static constexpr size_t CacheLineSize = std::hardware_destructive_interference_size; // The Stack defines its own Node with its own Next pointer struct Node { T Payload; std::atomic Next; }; // The pool manages the physical memory safely LockFreePool Pool; // The active head of our LIFO stack alignas(CacheLineSize) std::atomic Head{{NullIndex, 0}}; public: LockFreeStack(size_t Capacity) : Pool(Capacity) {} }; ``` Because we aligned our `Head` atomic to the `CacheLineSize`, we guarantee that threads competing to update the active stack will not trigger false sharing with threads competing to allocate memory from the pool's `FreeHead`. ## Lock-Free Push and Pop The free list we implemented for our object pool is also a lock-free stack, so we'll find an architectural symmetry here. _**Pushing**_ data onto a stack is mechanically identical to _**freeing**_ memory to an implicit free list. We point our new node's `Next` value to the current `Head`, and fire a CAS instruction to swing the `Head` to our new node. _**Popping**_ data from a stack is mechanically identical to _**allocating**_ memory from an implicit free list. We read the `Head`, find the next node in the chain, and fire a CAS instruction to swing the `Head` forward. Because we already wrote these exact CAS loops inside `LockFreePool` in the previous lesson, implementing `Push()` and `Pop()` becomes incredibly straightforward - we just repeat the pattern. ### Implementing `Push()` To push a new item, we ask the pool for an index. We write our payload into the pool, and then execute our standard `compare_exchange_weak()` loop. For now, we will rely on the default `std::memory_order_seq_cst` behavior for our atomic operations. We will strip away these heavy default fences in the tuning section later: ```c++ // ... template class LockFreeStack { // ... public: // ... bool Push(const T& Value) { // Grab am index from the allocator uint32_t NewIndex = Pool.Allocate(); if (NewIndex == NullIndex) return false; // Out of memory // Write the payload data Pool[NewIndex].Payload = Value; // Take a snapshot of the active stack TaggedIndex OldHead = Head.load(); TaggedIndex NewState; do { // Optimistically link our node to the current Head Pool[NewIndex].Next.store(OldHead.Index); // Prepare the new tagged state NewState = {NewIndex, OldHead.Tag + 1}; // Attempt the hardware CAS } while (!Head.compare_exchange_weak(OldHead, NewState)); return true; } }; ``` ### Implementing `Pop()` To pop an item, we read the `Head`, find the next node in the active chain, and swing the `Head` forward. Once we successfully claim the node via CAS, we read the payload and return the index to the pool. Because the pool guarantees memory is never unmapped, we are completely protected from segmentation faults: ```c++ // ... template class LockFreeStack { // ... public: // ... bool Pop(T& Result) { TaggedIndex OldHead = Head.load(); TaggedIndex NewState; do { // If the stack is empty, abort if (OldHead.Index == NullIndex) return false; // Prepare to swing the Head to the next node in the chain NewState = { Pool[OldHead.Index].Next.load(), OldHead.Tag + 1 }; } while (!Head.compare_exchange_weak(OldHead, NewState)); // We exclusively own the node now. Extract the data. Result = Pool[OldHead.Index].Payload; // Recycle the memory slot Pool.Free(OldHead.Index); return true; } }; ``` ## Usage Example Let's put our lock-free stack to the test by sharing it across a pool of threads. Below, we instantiate a single `LockFreeStack` and pass it by reference into four concurrent worker threads. Each worker pushes 100 uniquely identified items onto the stack, and then immediately turns around and pops 100 items off the stack. Because we are using a lock-free architecture, no thread is ever put to sleep by an OS mutex. The CPU cores simply spin locally, safely negotiating the `Head` pointer via hardware CAS instructions: ```c++ #include #include #include #include void WorkerThread(LockFreeStack& Stack, int ThreadID) { // Push heavily into the shared lock-free stack for (int i = 0; i < 100; ++i) { Stack.Push(ThreadID * 1000 + i); } // Pop heavily from the shared stack int Result; int SuccessCount = 0; for (int i = 0; i < 100; ++i) { if (Stack.Pop(Result)) { SuccessCount++; } } std::println( "Thread {} successfully popped {} items", ThreadID, SuccessCount ); } int main() { // Pre-allocate enough space for all threads LockFreeStack SharedStack(10000); { std::jthread t1(WorkerThread, std::ref(SharedStack), 1); std::jthread t2(WorkerThread, std::ref(SharedStack), 2); std::jthread t3(WorkerThread, std::ref(SharedStack), 3); std::jthread t4(WorkerThread, std::ref(SharedStack), 4); } std::println("All lock-free threads completed safely"); return 0; } ``` The exact order in which the threads finish will vary on every run based on OS scheduling, but the lock-free logic guarantees that exactly 400 items are pushed and successfully popped without a single data race, dropped payload, or ABA corruption: ```javascript // Thread 2 successfully popped 100 items Thread 1 successfully popped 100 items Thread 4 successfully popped 100 items Thread 3 successfully popped 100 items All lock-free threads completed safely ``` ## Benchmarking Let's prove that relying on the silicon's native CAS instruction out-scales operating system locks in high-contention environments. We will replicate a workload that interleaves pushing and popping with some arbitrary work. The `std::stack` implementation must aggressively halt threads when performing `push()` and `pop()`. Our `LockFreeStack` spins locally on the cache line without ever yielding control to the OS. ```c++ #include #include #include #include void SimulateWork(int cycles = 2000) { uint32_t dummy = 0; for (int i = 0; i < cycles; ++i) { benchmark::DoNotOptimize(dummy += i); } } std::stack MutexStack; std::mutex StackMutex; static void BM_MutexStack(benchmark::State& state) { for (auto _ : state) { state.PauseTiming(); { std::lock_guard lock(StackMutex); while (!MutexStack.empty()) MutexStack.pop(); } state.ResumeTiming(); // 32 threads fighting for the same Mutex for (int i = 0; i < 1000; ++i) { SimulateWork(); { std::lock_guard lock(StackMutex); MutexStack.push(i); } SimulateWork(); { std::lock_guard lock(StackMutex); if (!MutexStack.empty()) MutexStack.pop(); } } } } LockFreeStack LFStack(1'000'000); static void BM_LockFreeStack(benchmark::State& state) { for (auto _ : state) { state.PauseTiming(); int discard; while (LFStack.Pop(discard)) {} state.ResumeTiming(); // 32 threads spinning locally in CAS loops for (int i = 0; i < 1000; ++i) { SimulateWork(); LFStack.Push(i); SimulateWork(); int val; LFStack.Pop(val); } } } #define REGISTER_BENCHMARK(name) \ BENCHMARK(name) \ ->Threads(32) \ ->MeasureProcessCPUTime() \ ->Unit(benchmark::kMillisecond) REGISTER_BENCHMARK(BM_MutexStack); REGISTER_BENCHMARK(BM_LockFreeStack); ``` ```c++ // ------------------------------------------------------------ Benchmark Time CPU ------------------------------------------------------------ BM_MutexStack/process_time/threads:32 1.44 ms 31.7 ms BM_LockFreeStack/process_time/threads:32 0.473 ms 10.1 ms ``` Our basic, unoptimized, lock-free architecture already delivers a 3x performance improvement over `std::stack` in these tests. Because the OS scheduler is unaware of the contention, the threads remain awake, burning through the cycles much faster than the `std::mutex` equivalent. ## Tuning the Memory Order To squeeze maximum performance out of the silicon, we give the CPU more room to optimize our instruction ordering by loosing our memory fences from their `std::memory_order_seq_cst` defaults. The architectural symmetry between this lesson's stack the last lesson's free list applies to these memory orderings, too. Our `Push()` function will use the exact same fences as the pool's `Free()` function, and our `Pop()` function will use the same fences as the pool's `Allocate()` function. ### Provider: `Push()` When a thread calls `Push()`, it is acting as a **provider** of payload data to the main stack. We must ensure that the payload write is fully committed to physical RAM **before** the CAS publishes the new `Head` globally. To prevent the CPU's out-of-order execution engine from sinking the `Head` update below the payload write, we use a `release` fence on a successful CAS. Our initial load and the CAS failure outcome can safely remain `relaxed`, as no data is being published in those scenarios. ```c++ // ... template class LockFreeStack { // ... public: // ... bool Push(const T& Value) { uint32_t NewIndex = Pool.Allocate(); if (NewIndex == NullIndex) return false; Pool[NewIndex].Payload = Value; TaggedIndex OldHead = Head.load( std::memory_order_relaxed // ); TaggedIndex NewState; do { Pool[NewIndex].Next.store( OldHead.Index, std::memory_order_relaxed // ); NewState = {NewIndex, OldHead.Tag + 1}; } while (!Head.compare_exchange_weak( OldHead, NewState, // Publish the new node and its payload std::memory_order_release, // std::memory_order_relaxed // )); return true; } }; ``` ### Consumer: `Pop()` Conversely, `Pop()` is a **consumer** of the main stack. We must ensure that we do not extract the `Payload` before we have successfully synchronized with the thread that pushed it. We use `acquire` on our initial load and both CAS outcomes. This prevents the CPU from speculatively fetching the `Payload` prematurely, guaranteeing we only read the data after the CAS confirms we own the node. ```c++ // ... template class LockFreeStack { // ... public: // ... bool Pop(T& Result) { // Acquire the latest published node TaggedIndex OldHead = Head.load( std::memory_order_acquire // ); TaggedIndex NewState; do { if (OldHead.Index == NullIndex) return false; NewState = { Pool[OldHead.Index].Next.load( std::memory_order_relaxed // ), OldHead.Tag + 1 }; } while (!Head.compare_exchange_weak( OldHead, NewState, // Ensure payload extraction doesn't float above the CAS std::memory_order_acquire, // std::memory_order_acquire // )); Result = Pool[OldHead.Index].Payload; Pool.Free(OldHead.Index); return true; } }; ``` With these targeted memory fences, the CPU's execution pipeline can flow uninterrupted right up until the exact moment synchronization is strictly required. ## Complete Code Here is the complete implementation of our `LockFreeStack`, powered by our `LockFreePool`: ```c++ #pragma once #include constexpr uint32_t NullIndex = 0xFFFFFFFF; struct alignas(8) TaggedIndex { uint32_t Index; uint32_t Tag; }; ``` ```c++ #pragma once #include #include #include #include template class LockFreePool { private: static constexpr size_t CacheLineSize = std::hardware_destructive_interference_size; static_assert( std::atomic::is_always_lock_free, "Hardware does not support 64-bit lock-free atomics" ); struct alignas(CacheLineSize) Slot { T Payload; std::atomic FreeNext; }; std::vector Buffer; alignas(CacheLineSize) std::atomic FreeHead{{0, 0}}; public: LockFreePool(size_t Capacity) : Buffer(Capacity) { if (Capacity == 0 || Capacity >= NullIndex) { throw std::invalid_argument( "Capacity must be > 0 and < NullIndex" ); } for (size_t i = 0; i < Capacity - 1; ++i) { Buffer[i].FreeNext.store( i + 1, std::memory_order_relaxed ); } Buffer[Capacity - 1].FreeNext.store( NullIndex, std::memory_order_relaxed ); } uint32_t Allocate() { TaggedIndex OldFree = FreeHead.load( std::memory_order_acquire ); TaggedIndex NewFree; do { if (OldFree.Index == NullIndex) return NullIndex; NewFree = { Buffer[OldFree.Index].FreeNext.load( std::memory_order_relaxed ), OldFree.Tag + 1 }; } while (!FreeHead.compare_exchange_weak( OldFree, NewFree, std::memory_order_acquire, std::memory_order_acquire )); return OldFree.Index; } void Free(uint32_t TargetIndex) { TaggedIndex OldFree = FreeHead.load( std::memory_order_relaxed ); TaggedIndex NewFree; do { Buffer[TargetIndex].FreeNext.store( OldFree.Index, std::memory_order_relaxed ); NewFree = {TargetIndex, OldFree.Tag + 1}; } while (!FreeHead.compare_exchange_weak( OldFree, NewFree, std::memory_order_release, std::memory_order_relaxed )); } T& operator[](uint32_t Index) { return Buffer[Index].Payload; } }; ``` ```c++ #pragma once #include #include #include #include #include template class LockFreeStack { private: static_assert( std::is_nothrow_copy_assignable_v, "Type T must not throw to guarantee exception safety" ); static constexpr size_t CacheLineSize = std::hardware_destructive_interference_size; struct Node { T Payload; std::atomic Next; }; LockFreePool Pool; alignas(CacheLineSize) std::atomic Head{{NullIndex, 0}}; public: LockFreeStack(size_t Capacity) : Pool(Capacity) {} bool Push(const T& Value) { uint32_t NewIndex = Pool.Allocate(); if (NewIndex == NullIndex) return false; Pool[NewIndex].Payload = Value; TaggedIndex OldHead = Head.load(std::memory_order_relaxed); TaggedIndex NewState; do { Pool[NewIndex].Next.store( OldHead.Index, std::memory_order_relaxed ); NewState = {NewIndex, OldHead.Tag + 1}; } while (!Head.compare_exchange_weak( OldHead, NewState, std::memory_order_release, std::memory_order_relaxed )); return true; } bool Pop(T& Result) { TaggedIndex OldHead = Head.load(std::memory_order_acquire); TaggedIndex NewState; do { if (OldHead.Index == NullIndex) return false; NewState = { Pool[OldHead.Index].Next.load(std::memory_order_relaxed), OldHead.Tag + 1 }; } while (!Head.compare_exchange_weak( OldHead, NewState, std::memory_order_acquire, std::memory_order_acquire )); Result = Pool[OldHead.Index].Payload; Pool.Free(OldHead.Index); return true; } }; ``` ```c++ #include #include #include #include void WorkerThread(LockFreeStack& Stack, int ThreadID) { // Push heavily into the shared lock-free stack for (int i = 0; i < 100; ++i) { Stack.Push(ThreadID * 1000 + i); } // Pop heavily from the shared stack int Result; int SuccessCount = 0; for (int i = 0; i < 100; ++i) { if (Stack.Pop(Result)) { SuccessCount++; } } std::println( "Thread {} successfully popped {} items", ThreadID, SuccessCount ); } int main() { LockFreeStack SharedStack(10000); { std::jthread t1(WorkerThread, std::ref(SharedStack), 1); std::jthread t2(WorkerThread, std::ref(SharedStack), 2); std::jthread t3(WorkerThread, std::ref(SharedStack), 3); std::jthread t4(WorkerThread, std::ref(SharedStack), 4); } std::println("All lock-free threads completed safely"); return 0; } ``` ## Summary In this lesson, we completed our lock-free LIFO container. 1. By relying on `LockFreePool`, we completely sidestepped the physical memory traps of segmentation faults and ABA corruption. 2. We used the hardware's native CAS instruction to swing a `Head` index safely across multiple CPU cores without ever invoking an OS mutex. 3. We observed the mechanical symmetry between the data structure and its allocator. Pushing to a stack acts just like freeing to a pool; popping from a stack acts just like allocating from a pool. 4. We optimized our algorithms by replacing heavy `seq_cst` fences with surgical `acquire` and `release` barriers, allowing the CPU's out-of-order execution engine to make safe optimizations.

Lock-Free Stacks

Understanding the Basics

Practical Applications

Common Mistakes

Next Steps

Additional Resources

Assessment Preparation