In the , 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.

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:

1#include <stack>
2#include <mutex>
3
4std::stack<int> TaskStack;
5std::mutex StackMutex;
6
7void AddTask(int TaskID) {
8  std::lock_guard<std::mutex> lock(StackMutex); 
9  TaskStack.push(TaskID);
10}

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.

dsa_core/include/dsa/LockFreeStack.h

1#pragma once
2#include <atomic>
3#include <new>
4#include <type_traits>
5#include <dsa/TaggedIndex.h>
6#include <dsa/LockFreePool.h>
7
8template <typename T>
9class LockFreeStack {
10private:
11  static_assert(
12    std::is_nothrow_copy_assignable_v<T>,
13    "Type T must not throw to guarantee exception safety"
14  );
15  
16  static constexpr size_t CacheLineSize =
17    std::hardware_destructive_interference_size;
18
19  // The Stack defines its own Node with its own Next pointer
20  struct Node {
21    T Payload;
22    std::atomic<uint32_t> Next;
23  };
24
25  // The pool manages the physical memory safely
26  LockFreePool<Node> Pool;
27
28  // The active head of our LIFO stack
29  alignas(CacheLineSize)
30    std::atomic<TaggedIndex> Head{{NullIndex, 0}};
31
32public:
33  LockFreeStack(size_t Capacity) : Pool(Capacity) {}
34};

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:

dsa_core/include/dsa/LockFreeStack.h

1// ...
2
3template <typename T>
4class LockFreeStack {
5  // ...
6
7public:
8  // ...
9  bool Push(const T& Value) {
10    // Grab am index from the allocator
11    uint32_t NewIndex = Pool.Allocate();
12    if (NewIndex == NullIndex) return false; // Out of memory
13
14    // Write the payload data
15    Pool[NewIndex].Payload = Value;
16
17    // Take a snapshot of the active stack
18    TaggedIndex OldHead = Head.load();
19    TaggedIndex NewState;
20
21    do {
22      // Optimistically link our node to the current Head
23      Pool[NewIndex].Next.store(OldHead.Index);
24
25      // Prepare the new tagged state
26      NewState = {NewIndex, OldHead.Tag + 1};
27
28      // Attempt the hardware CAS
29    } while (!Head.compare_exchange_weak(OldHead, NewState));
30
31    return true;
32  }
33};

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:

dsa_core/include/dsa/LockFreeStack.h

1// ...
2
3template <typename T>
4class LockFreeStack {
5  // ...
6
7public:
8  // ...
9  bool Pop(T& Result) {
10    TaggedIndex OldHead = Head.load();
11    TaggedIndex NewState;
12
13    do {
14      // If the stack is empty, abort
15      if (OldHead.Index == NullIndex) return false;
16
17      // Prepare to swing the Head to the next node in the chain
18      NewState = {
19        Pool[OldHead.Index].Next.load(),
20        OldHead.Tag + 1
21      };
22
23    } while (!Head.compare_exchange_weak(OldHead, NewState));
24
25    // We exclusively own the node now. Extract the data.
26    Result = Pool[OldHead.Index].Payload;
27
28    // Recycle the memory slot
29    Pool.Free(OldHead.Index);
30    return true;
31  }
32};

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:

dsa_app/main.cpp

1#include <print>
2#include <thread>
3#include <vector>
4#include <dsa/LockFreeStack.h>
5
6void WorkerThread(LockFreeStack<int>& Stack, int ThreadID) {
7  // Push heavily into the shared lock-free stack
8  for (int i = 0; i < 100; ++i) {
9    Stack.Push(ThreadID * 1000 + i);
10  }
11
12  // Pop heavily from the shared stack
13  int Result;
14  int SuccessCount = 0;
15  for (int i = 0; i < 100; ++i) {
16    if (Stack.Pop(Result)) {
17      SuccessCount++;
18    }
19  }
20
21  std::println(
22    "Thread {} successfully popped {} items",
23    ThreadID, SuccessCount
24  );
25}
26
27int main() {
28  // Pre-allocate enough space for all threads
29  LockFreeStack<int> SharedStack(10000);
30
31  {
32    std::jthread t1(WorkerThread, std::ref(SharedStack), 1);
33    std::jthread t2(WorkerThread, std::ref(SharedStack), 2);
34    std::jthread t3(WorkerThread, std::ref(SharedStack), 3);
35    std::jthread t4(WorkerThread, std::ref(SharedStack), 4);
36  }
37
38  std::println("All lock-free threads completed safely");
39  return 0;
40}

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:

1Thread 2 successfully popped 100 items
2Thread 1 successfully popped 100 items
3Thread 4 successfully popped 100 items
4Thread 3 successfully popped 100 items
5All 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.

benchmarks/main.cpp

1#include <benchmark/benchmark.h>
2#include <stack>
3#include <mutex>
4#include <dsa/LockFreeStack.h>
5
6void SimulateWork(int cycles = 2000) {
7  uint32_t dummy = 0;
8  for (int i = 0; i < cycles; ++i) {
9    benchmark::DoNotOptimize(dummy += i);
10  }
11}
12
13std::stack<int> MutexStack;
14std::mutex StackMutex;
15
16static void BM_MutexStack(benchmark::State& state) {
17  for (auto _ : state) {
18    state.PauseTiming();
19    {
20      std::lock_guard<std::mutex> lock(StackMutex);
21      while (!MutexStack.empty()) MutexStack.pop();
22    }
23    state.ResumeTiming();
24
25    // 32 threads fighting for the same Mutex
26    for (int i = 0; i < 1000; ++i) {
27      SimulateWork();
28      {
29        std::lock_guard<std::mutex> lock(StackMutex);
30        MutexStack.push(i);
31      }
32      SimulateWork();
33      {
34        std::lock_guard<std::mutex> lock(StackMutex);
35        if (!MutexStack.empty()) MutexStack.pop();
36      }
37    }
38  }
39}
40
41LockFreeStack<int> LFStack(1'000'000);
42
43static void BM_LockFreeStack(benchmark::State& state) {
44  for (auto _ : state) {
45    state.PauseTiming();
46    int discard;
47    while (LFStack.Pop(discard)) {}
48    state.ResumeTiming();
49
50    // 32 threads spinning locally in CAS loops
51    for (int i = 0; i < 1000; ++i) {
52      SimulateWork();
53      LFStack.Push(i);
54      SimulateWork();
55      int val;
56      LFStack.Pop(val);
57    }
58  }
59}
60
61#define REGISTER_BENCHMARK(name) \
62  BENCHMARK(name)                \
63    ->Threads(32)                \
64    ->MeasureProcessCPUTime()    \
65    ->Unit(benchmark::kMillisecond)
66
67REGISTER_BENCHMARK(BM_MutexStack);
68REGISTER_BENCHMARK(BM_LockFreeStack);

1------------------------------------------------------------
2Benchmark                                     Time       CPU
3------------------------------------------------------------
4BM_MutexStack/process_time/threads:32      1.44 ms   31.7 ms
5BM_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.

dsa_core/include/dsa/LockFreeStack.h

1// ...
2
3template <typename T>
4class LockFreeStack {
5// ...
6public:
7  // ...
8  bool Push(const T& Value) {
9    uint32_t NewIndex = Pool.Allocate();
10    if (NewIndex == NullIndex) return false;
11
12    Pool[NewIndex].Payload = Value;
13
14    TaggedIndex OldHead = Head.load(
15      std::memory_order_relaxed 
16    );
17    TaggedIndex NewState;
18
19    do {
20      Pool[NewIndex].Next.store(
21        OldHead.Index,
22        std::memory_order_relaxed 
23      );
24      NewState = {NewIndex, OldHead.Tag + 1};
25
26    } while (!Head.compare_exchange_weak(
27      OldHead, NewState,
28      // Publish the new node and its payload
29      std::memory_order_release, 
30      std::memory_order_relaxed  
31    ));
32
33    return true;
34  }
35};

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.

dsa_core/include/dsa/LockFreeStack.h

1// ...
2
3template <typename T>
4class LockFreeStack {
5// ...
6public:
7  // ...
8  bool Pop(T& Result) {
9    // Acquire the latest published node
10    TaggedIndex OldHead = Head.load(
11      std::memory_order_acquire 
12    );
13    TaggedIndex NewState;
14
15    do {
16      if (OldHead.Index == NullIndex) return false;
17
18      NewState = {
19        Pool[OldHead.Index].Next.load(
20          std::memory_order_relaxed 
21        ),
22        OldHead.Tag + 1
23      };
24
25    } while (!Head.compare_exchange_weak(
26      OldHead, NewState,
27      // Ensure payload extraction doesn't float above the CAS
28      std::memory_order_acquire, 
29      std::memory_order_acquire  
30    ));
31
32    Result = Pool[OldHead.Index].Payload;
33    Pool.Free(OldHead.Index);
34    return true;
35  }
36};

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:

Files

dsa_core

dsa_app

Select a file to view its content

Summary

In this lesson, we completed our lock-free LIFO container.

By relying on LockFreePool, we completely sidestepped the physical memory traps of segmentation faults and ABA corruption.
We used the hardware's native CAS instruction to swing a Head index safely across multiple CPU cores without ever invoking an OS mutex.
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.
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

Recommended Reading

The LIFO Contention Problem

Treiber Stacks

dsa_core/include/dsa/LockFreeStack.h

Lock-Free Push and Pop

Implementing `Push()`

dsa_core/include/dsa/LockFreeStack.h

Implementing `Pop()`

dsa_core/include/dsa/LockFreeStack.h

Usage Example

dsa_app/main.cpp

Benchmarking

benchmarks/main.cpp

Tuning the Memory Order

Provider: `Push()`

dsa_core/include/dsa/LockFreeStack.h

Consumer: `Pop()`

dsa_core/include/dsa/LockFreeStack.h

Complete Code

Files

Summary

Practical DSA

Lock-Free Stacks

Recommended Reading

The LIFO Contention Problem

Treiber Stacks

dsa_core/include/dsa/LockFreeStack.h

Lock-Free Push and Pop

Implementing Push()

dsa_core/include/dsa/LockFreeStack.h

Implementing Pop()

dsa_core/include/dsa/LockFreeStack.h

Usage Example

dsa_app/main.cpp

Benchmarking

benchmarks/main.cpp

Tuning the Memory Order

Provider: Push()

dsa_core/include/dsa/LockFreeStack.h

Consumer: Pop()

dsa_core/include/dsa/LockFreeStack.h

Complete Code

Files

Summary

Implementing `Push()`

Implementing `Pop()`

Provider: `Push()`

Consumer: `Pop()`