Lock-Free Pointers

In the previous lessons, we built optimistic transactions using the hardware's Compare-And-Swap (CAS) instruction. We learned how to pull a struct into our local CPU registers, perform complex math, and publish the result using compare_exchange_weak().

As long as our struct fits inside a 64-bit or 128-bit native register, the CPU guarantees that our updates are absolutely atomic and lock-free. But what happens when our data doesn't fit into a CPU register? To build lock-free algorithms in this context, we often need aim our CAS instructions at pointers to data rather than the data itself.

In this lesson, we will uncover why lock-free pointers are a hardware minefield. We will expose the physical realities of the global memory allocator, visualize the use-after-free trap, and revisit the infamous ABA Problem.

In our earlier examples, we used CAS on basic integers and small state structs. When the CPU executes a CAS instruction on an integer, it compares the numerical bits. If the bits match, the mathematical state of the program has not changed, and it is completely safe to execute the swap.

But a pointer is just a 64-bit hexadecimal integer that represents a physical memory address.

When we ask the CPU to execute a CAS instruction on a std::atomic<Node*>, the silicon checks the 64-bit address. It does not check the data at that address. The CPU has absolutely no idea if the node being pointed to has been modified, corrupted, or entirely deleted by another thread.

To see why this is so dangerous, let's look at a naive attempt to write a lock-free Pop() function that removes the element at the Head of a linked list:

1#include <atomic>
2
3struct Node {
4  int Value;
5  Node* Next;
6};
7
8std::atomic<Node*> Head;
9
10int NaivePop() {
11  // Take a snapshot of the top of the list
12  Node* Expected = Head.load();
13
14  do {
15    if (Expected == nullptr) {
16      return -1; // The list is empty
17    }
18
19    // Attempt to swing the Head pointer to the Next node.
20    // If Head still equals Expected, overwrite Head with Next
21  } while (!Head.compare_exchange_weak(
22    Expected,
23    Expected->Next 
24  ));
25
26  int Result = Expected->Value;
27  delete Expected; 
28  return Result;
29}

At first glance, this looks identical to the optimistic CAS loops we wrote previously. We read the Expected state, we determine the Desired state (which is Expected->Next), and we attempt the swap.

Unfortunately, this code is a ticking time bomb.

The vulnerability lies within the condition of the while loop, specifically when we attempt to evaluate Expected->Next.

1do {
2   // ...
3} while (!Head.compare_exchange_weak(
4  Expected,
5  Expected->Next 
6));

Between the moment our thread loads Expected from memory and the moment it attempts to read the Next pointer inside that node, we have a race window. Let's step through exactly how the OS scheduler can turn this tiny window into a crash:

Thread 1 blindly reaches across the memory bus to read Expected->Next. But Expected is pointing to Node A, which has been obliterated.

The CPU attempts to access an invalid or unmapped memory address. The hardware triggers a page fault, the operating system catches the illegal access, and our application is terminated with a segmentation fault.

This is the classic use-after-free bug. In a lock-free environment, we cannot safely dereference a pointer if there is even a fractional chance that another thread might be concurrently deleting it.

Suppose we recognize the use-after-free trap, and we find a workaround. We'll implement one of those workarounds in the next chapter but, for now, let's just imagine we've done that and Thread 1 can safely evaluate Expected->Next without any use-after-free risk.

We then immediately run into a second issue: the return of the ABA problem we covered earlier in the course in a slightly different context.

The CAS loop ensures the Expected->Next pointer hasn't changed, but it doesn't check that the thing it is pointing at hasn't changed.

The CAS instruction only looks at the 64-bit hexadecimal memory address. It saw the memory address for Node A at the Head of the list, and it saw the memory address for Node A in Thread 1's register.

The CPU concluded: "The addresses match perfectly! Nothing has changed!"

It executed the swap, overwriting Head with Thread 1's desired value: Node B. But Node B was completely destroyed.

The Head of our list is now pointing to corrupted, recycled garbage memory. Our data structure is shattered, but the program simply continues running with silently corrupted memory.

Why Allocators Recycle

When learning about the ABA problem, many engineers have the same reaction: "what are the odds of that actually happening?"

Why would the memory allocator give Node A back to us so quickly? If we have gigabytes of free RAM, shouldn't the allocator give us a brand new, never-before-used memory address, reducing the risk of ABA collisions?

In reality, the hardware and the allocator are often optimizing for cache locality. They actively conspire to recycle memory addresses as aggressively as possible, making ABA issues extremely likely if we don't actively mitigate against it.

If a thread just finished using a piece of memory a few microseconds ago, that memory is physically sitting inside the CPU core's ultra-fast L1 cache. If we immediately asks for a new Node(), the absolute fastest thing the allocator can do is hand back the exact same memory address it just freed.

If the memory address alone isn't enough to prove the node hasn't changed, we need more information. We can solve this manifestation of the ABA problem in a very similar way we solved it for array indices earlier in the course by creating a handle that combines the array index with a version tag .

Combining a pointer with a version tag looks very similar:

1#include <cstdint>
2
3// Align to 16 bytes (128 bits)
4struct alignas(16) TaggedPointer {
5  Node* Ptr;
6  uint64_t Version;
7};
8
9std::atomic<TaggedPointer> Head;

Every time we update the pointer or push it to a list, we also increment the version number.

Even if the memory address is recycled to create an ABA scenario, the version number will have progressed from 1 (A) to 2 (B) to 3 (A). The combined state A1 does not match A3, so the CAS instruction will correctly fail.

However, as we saw earlier, we need to be cautious about how much data we try to stuff into a std::atomic. On a 64-bit operating system, a standard pointer is 64 bits. If we combine it with any other data, it no longer fits within a 64-bit register.

To update our 128-bit TaggedPointer safely, we need the CPU to perform a Double-Width Compare-and-Swap (DWCAS). Most modern desktop and server processors support this, but earlier processors and some modern mobile ARM chips don't.

We can check if our target architecture natively supports this using the atomic's is_always_lock_free flag:

1static_assert(
2  std::atomic<TaggedPointer>::is_always_lock_free, 
3  "Hardware does not natively support 128-bit CAS"
4);

If we compile a std::atomic using a 128-bit type for a chip that lacks 128-bit CAS, the standard library will quietly inject a hidden std::mutex into our wrapper to maintain the atomic behaviour. We will lose all the performance benefits of our lock-free design, suffering from OS context switches every time we touch the pointer.

In the next chapter, we will create a lock-free linked list that combine this TaggedPointer technique with the index-based links we covered previously. This means we can reduce the size of our struct to 64 bits - 32 bits for the index, and 32 bits for the version.

If 128-bit DWCAS isn't perfectly portable, what other options are there? We need to implement an architecture that follows a golden rule: never physically delete memory if there is any chance another thread might be looking at it.

If memory is never freed while references exist, use-after-free is impossible. If memory is never returned to the allocator, it can never be recycled, making the ABA problem impossible. But we can't just let our programs consume infinite RAM. We need a way to logically remove a node from the data structure, but defer its physical destruction until we can be certain that every single thread has finished looking at it.

This concept is called safe memory reclamation (SMR), and it requires complex architectural patterns to manage. Two common approaches are:

1. Hazard Pointers: Threads announce which specific memory addresses they are currently using by placing them in a globally visible "hazard" list. Before another thread calls delete, it checks the hazard list. If the address is there, the deletion is deferred.
2. Epoch-Based Reclamation: The application is divided into epochs. New epochs might start on a time interval, or after every frame in a game engine, or after every batch of transactions in a data service. When a node is removed, it is tagged with the current epoch. Memory is only physically deleted when all threads announce they have safely progressed to the next epoch.

In this lesson, we discovered why taking optimistic lock-free logic and aiming it at raw pointers is inherently dangerous.

1. The Pointer Limit: We learned that CAS only verifies the numerical 64-bit memory address, remaining entirely blind to the actual data contents living at that address.
2. Use-After-Free: We visualized the fatal race window in naive lock-free loops. Dereferencing a pointer that a suspended thread expects to be valid often results in an OS-level segmentation fault if another thread deletes it.
3. The ABA Problem: We explored how a CAS instruction can be tricked if a memory address is popped, deleted, and then re-allocated for a new node.
4. Cache Warmth: We realized that the ABA problem is not a statistical anomaly. Modern thread-local allocators aggressively recycle hot L1 cache lines, practically guaranteeing address reuse.
5. Double-Word CAS: We reviewed the workaround of adding a version tag to the pointer, which often requires 128-bit hardware instructions that lack universal portability.

Now that we understand the physical constraints of memory and thread execution, we are ready to build a true, production-grade lock-free container.

In the next lesson, we will combine optimistic CAS loops with generational indexing. We will build a lock-free Treiber Stack, eliminating the ABA problem and outperforming standard mutex-locked queues in high-contention environments.