Lock-Free Object Pools

In the previous lessons, we used Compare-And-Swap (CAS) loops to build fast data pipelines across CPU cores. But our MPMC queue was a fixed-size ring buffer. What happens when we want to build an unbounded structure, like a dynamically growing stack or list?

When we attempt to apply optimistic concurrency to dynamic memory, we run into a brick wall of hardware realities.

Over the next two lessons, we'll build a lock-free stack that can scale up as much as we want. In this first part, we will focus on the allocation problem. We will build a thread-safe, lock-free memory pool that prevents segmentation faults and defeats the corruption of the ABA problem.

Recommended Reading

This is a relatively advanced lesson, pulling together many techniques we covered in the previous chapters. To follow along, being particularly comfortable with the following topics is highly recommended:

• Implementing and using an object pool , including an implicit free list to track the available slots
• Implementing custom atomic logic using compare-and-swap (CAS)
• The challenges of working with lock-free pointers
• Implementing a container that supports the MPMC access pattern

If we want to build a lock-free stack, our first instinct is to allocate nodes on the global heap using new, and use a CAS loop to swing a Head pointer. Let's look at a naive attempt to Pop() a node from a standard linked list:

1int NaivePop() {
2  Node* Expected = Head.load();
3
4  do {
5    if (Expected == nullptr) return -1;
6
7    // DANGER: If another thread deletes 'Expected' right now,
8    // accessing Expected->Next will trigger a crash
9  } while (!Head.compare_exchange_weak(
10    Expected,
11    Expected->Next 
12  ));
13
14  int Result = Expected->Payload;
15  delete Expected; 
16  return Result;
17}

This code is a ticking time bomb. Between the moment our thread reads Expected from memory and the moment we attempt to evaluate Expected->Next, we have a race window:

Thread 1 blindly reaches across the memory bus to read Expected->Next. But Expected is pointing to Node A, which has been freed by Thread 2's call to delete.

The CPU attempts to access an invalid, unmapped memory address. The operating system catches the illegal access, and our application is terminated with a segmentation fault (use-after-free).

Eliminating Use-After-Free

This limitation dictates a golden rule for lock-free programming: we must never return memory to the operating system if there is even a fractional chance another thread is using it.

If we never call delete, we never unmap the virtual address, and the CPU will never trigger a segmentation fault. To achieve this, we will resurrect the Object Pool we built earlier in the course.

By pre-allocating a massive block of memory and managing an implicit free list, the memory remains permanently owned by our application. Even if a node is logically "popped" and returned to the free list, its physical bytes remain mapped and safe for a sleeping thread to read.

Let's begin scaffolding our LockFreePool. The initial setup is almost identical to the MPMC buffer from the previous lesson. There are only two key changes:

• We don't need to keep track of the Tail - we'll always push and pop slots from the Head of our free list.
• We don't need the Capacity or Mask. The capacity of our object pool will be set in the constructor, which we implement in the next section

Defining our key variables would look something like this:

1#pragma once
2#include <vector>
3#include <atomic>
4#include <new>
5
6template <typename T>
7class LockFreePool {
8private:
9  static constexpr size_t CacheLineSize =
10    std::hardware_destructive_interference_size;
11    
12  static constexpr uint32_t NullIndex = 0xFFFFFFFF;
13
14  struct alignas(CacheLineSize) Slot {
15    T Payload;
16    std::atomic<uint32_t> FreeNext;
17  };
18
19  std::vector<Slot> Buffer;
20  alignas(CacheLineSize) std::atomic<uint32_t> FreeHead{0};
21};

The Constructor

Our constructor matches the logic of the single-threaded object pool we implemented in the earlier chapter. Every slot is initially free, so we weave our free list through every index in the buffer:

1// ...
2
3template <typename T>
4class LockFreePool {
5private:
6  // ...
7
8public:
9  LockFreePool(size_t Capacity) : Buffer(Capacity) {
10    if (Capacity == 0 || Capacity >= NullIndex) {
11      throw std::invalid_argument("Invalid Capacity");
12    }
13
14    // Because this runs sequentially on boot, we don't
15    // need CAS loops to wire the initial free list
16    for (size_t i = 0; i < Capacity - 1; ++i) {
17      Buffer[i].FreeNext.store(i + 1);
18    }
19    Buffer[Capacity - 1].FreeNext.store(NullIndex);
20  }
21};

By replacing pointers with indices, we have solved the segmentation fault. A thread reading Buffer[OldFree].FreeNext will always hit valid memory.

But we have another vulnerability: the ABA Problem.

Because we aggressively recycle slots using our internal free list, an index can be allocated, freed, and allocated again in a matter of microseconds. If a thread pauses at the wrong moment, the CAS instruction will be tricked:

Thread 1 just set the data structure's Head to Index 1 - an index that currently belongs to the free list. Our active data structure and our free list are now permanently cross-linked. Future allocations will overwrite live data, creating infinite loops and destroying the application.

The CAS instruction only compared the 32-bit integer 0. It saw 0, and assumed the state of the world had not changed. It didn't realize it was looking at a brand new 0.

Defeating ABA with Tagged Indices

To defeat ABA, we add a generation tag to our indices, just like we did in our Structure-of-Arrays systems earlier in the course .

Every time an index passes through our FreeHead, we increment a counter. Instead of asking the CAS if FreeHead == 0, we ask if FreeHead == 0 AND Generation == 5.

Let's bundle our index and a tag into a single struct:

1#pragma once
2#include <cstdint>
3
4constexpr uint32_t NullIndex = 0xFFFFFFFF;
5
6// 64-bit struct perfectly sized for a single hardware register
7struct alignas(8) TaggedIndex {
8  uint32_t Index;
9  uint32_t Tag;
10};

Because our TaggedIndex consists of two 32-bit integers and is explicitly 8-byte aligned, a 64-bit CPU can pack this entire struct into a single hardware register. This allows us to perform a native, lock-free CAS on both the index and the version tag simultaneously.

Let's integrate this into our pool. We add a static_assert to ensure the compiler hasn't betrayed us by quietly injecting an OS lock to handle the 64-bit struct:

1// ...
2#include <dsa/TaggedIndex.h>
3
4template <typename T>
5class LockFreePool {
6private:
7  // ...
8  static_assert(
9    std::atomic<TaggedIndex>::is_always_lock_free,
10    "Hardware does not support 64-bit lock-free atomics"
11  );
12
13  struct alignas(CacheLineSize) Slot {
14    T Payload;
15    std::atomic<uint32_t> FreeNext;
16  };
17
18  std::vector<Slot> Buffer;
19
20  // FreeHead now tracks both the index and the ABA tag
21  alignas(CacheLineSize) std::atomic<TaggedIndex> FreeHead{{0, 0}};
22
23  // ...
24};

We can now implement our thread-safe memory management using optimistic CAS loops .

Implementing Allocate()

To Allocate(), we read the current FreeHead state. We identify the next free slot in the chain. We bundle that next slot with an incremented tag, and attempt to swing the FreeHead forward.

1// ...
2
3template <typename T>
4class LockFreePool {
5// ...
6public:
7  // ...
8
9  uint32_t Allocate() {
10    TaggedIndex OldFree = FreeHead.load();
11    TaggedIndex NewFree;
12
13    do {
14      if (OldFree.Index == NullIndex) return NullIndex;
15
16      // Prepare our desired state: the next index,
17      // and an incremented ABA tag
18      NewFree = {
19        Buffer[OldFree.Index].FreeNext.load(),
20        OldFree.Tag + 1
21      };
22
23    } while (!FreeHead.compare_exchange_weak(
24      OldFree,
25      NewFree
26    ));
27
28    return OldFree.Index;
29  }
30};

Implementing Free()

To Free() a slot, we do the exact reverse. We take the index we want to return, wire its FreeNext value to point to the current FreeHead, and use a CAS loop to push it onto the top of the stack, again incrementing the tag to permanently alter its physical signature.

1// ...
2
3template <typename T>
4class LockFreePool {
5// ...
6public:
7  // ...
8
9  void Free(uint32_t TargetIndex) {
10    TaggedIndex OldFree = FreeHead.load();
11    TaggedIndex NewFree;
12
13    do {
14      // Wire the dying slot to point to the current free list
15      Buffer[TargetIndex].FreeNext.store(OldFree.Index);
16
17      // Prepare to push it to the top
18      NewFree = {
19        TargetIndex,
20        OldFree.Tag + 1
21      };
22
23    } while (!FreeHead.compare_exchange_weak(
24      OldFree,
25      NewFree
26    ));
27  }
28
29  // Provide simple access to the payload data
30  T& operator[](uint32_t Index) {
31    return Buffer[Index].Payload;
32  }
33};

Implementing the [] Operator

Finally, let's give users a convenient way to access the payloads they're storing in our pool:

1// ...
2
3template <typename T>
4class LockFreePool {
5// ...
6public:
7  // ...
8
9  // Provide simple access to the payload data
10  T& operator[](uint32_t Index) {
11    return Buffer[Index].Payload;
12  }
13};

Currently, every std::atomic operation in our class is implicitly using std::memory_order_seq_cst. As we learned previously , this default setting drops a massive memory fence that completely halts the CPU pipeline across all cores to enforce strict chronological consensus.

If we need to squeeze maximum performance out of the silicon, we can loosen these restrictions using acquire and release fences, or remove them entirely using relaxed.

Consumer: Allocate()

When a thread calls Allocate(), it is acting as a consumer of the free list. It needs to read OldFree and extract FreeNext safely.

We use acquire to synchronize with the thread that previously freed the slot. This guarantees the CPU will not speculatively read FreeNext out of order before we have officially claimed ownership of the FreeHead:

1// ...
2
3template <typename T>
4class LockFreePool {
5// ...
6public:
7  // ...
8  uint32_t Allocate() {
9    // Acquire the latest published state of the free list
10    TaggedIndex OldFree = FreeHead.load(
11      std::memory_order_acquire 
12    );
13    TaggedIndex NewFree;
14
15    do {
16      if (OldFree.Index == NullIndex) return NullIndex;
17
18      NewFree = {
19        Buffer[OldFree.Index].FreeNext.load(
20          std::memory_order_relaxed 
21        ),
22        OldFree.Tag + 1
23      };
24
25    } while (!FreeHead.compare_exchange_weak(
26      OldFree, NewFree,
27      std::memory_order_acquire, 
28      std::memory_order_acquire  
29    ));
30
31    return OldFree.Index;
32  }
33  // ...
34};

Provider: Free()

When a thread calls Free(), it is acting as a provider to the free list. It updates the internal FreeNext value, and then publishes the slot globally to the FreeHead.

To prevent the CPU from sinking our FreeNext write below the atomic CAS (which would cause an allocating thread to read stale data), we use a release fence on a successful CAS:

1// ...
2
3template <typename T>
4class LockFreePool {
5// ...
6public:
7  // ...
8  void Free(uint32_t TargetIndex) {
9    TaggedIndex OldFree = FreeHead.load(
10      std::memory_order_relaxed 
11    );
12    TaggedIndex NewFree;
13
14    do {
15      Buffer[TargetIndex].FreeNext.store(
16        OldFree.Index,
17        std::memory_order_relaxed 
18      );
19      NewFree = {TargetIndex, OldFree.Tag + 1};
20
21    } while (!FreeHead.compare_exchange_weak(
22      OldFree, NewFree,
23      std::memory_order_release, 
24      std::memory_order_relaxed  
25    ));
26  }
27  // ...
28};

Here is the complete implementation of our LockFreePool:

In this lesson, we established the foundational bedrock required to build unbounded, lock-free node structures.

1. Use-After-Free: We walked through the race window in naive lock-free loops. Dereferencing a pointer that a suspended thread expects to be valid results in a segmentation fault if another thread deletes it.
2. The Lock-Free Pool: By wrapping payloads in a Slot and managing an implicit free list, we guarantee memory is never physically returned to the OS, neutralizing the use-after-free risk.
3. The ABA Problem: We explored how rapid index recycling tricks the CAS instruction into corrupting active data structures.
4. Tagged Indices: By packing a version tag alongside our index into an 8-byte TaggedIndex struct, we forced a physical signature change on every allocation, defeating the ABA problem.

In the next lesson, we will put this allocator to work. We will build a highly concurrent LIFO container - the Treiber Stack.