Advanced Thread Safety in C++
Tags: cpp
Published: 2023-07-13 12:53:11

---
title: Advanced Thread Safety in C++
published: true
description: Beyond mutexes and locks with atomic and memory barriers.
tags: cpp
# cover_image: https://direct_url_to_image.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2023-07-07 02:10 +0000
---

## Introduction

C++ supports writing programs where parts of the code run concurrently using [threads](https://en.wikipedia.org/wiki/Thread_(computing)).  When writing such programs, you have to take additional steps to ensure that data shared among threads can not cause [race conditions](https://en.wikipedia.org/wiki/Race_condition). Typically, race conditions are avoided by proper use of [mutexes](https://en.wikipedia.org/wiki/Mutual_exclusion) and [locks](https://en.wikipedia.org/wiki/Lock_(computer_science)). However, in high-performance code, mutexes can sometimes be too costly, especially with high-contention data. C++ supports alternatives.

Note: what follows will _not_ describe how to [create](https://en.cppreference.com/w/cpp/thread/thread/thread) or [join](https://en.cppreference.com/w/cpp/thread/thread/join) [threads](https://en.cppreference.com/w/cpp/thread/thread) since those things are largely straightforward. Instead, what follows will describe how to write programs safely in a multithreaded program.

## A Brief History

In the late 1960s, early 1970s, programs (running on computers such as the [PDP-7](https://en.wikipedia.org/wiki/PDP-7) and later the [PDP-11](https://en.wikipedia.org/wiki/PDP-11)) were:

+ Single-threaded. (While nascent “threads” appeared in 1966, [POSIX threads](https://en.wikipedia.org/wiki/Pthreads) didn’t arrive until 1995.)
+ Executed sequentially.  (That is, machine code instructions generated by compilers were executed one at a time and in the same order as the original statements in your program were written.)
+ Running in flat (non-hierarchical) memory.  (CPU caches didn’t exist until the late 1970s and didn’t go mainstream until 1993 with the [Intel Pentium](https://en.wikipedia.org/wiki/Pentium_(original)).)

While CPU performance was increasing rapidly, memory performance lagged:

![CPU-Memory Performance Gap](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7sddsz96qfcv5v9yx5yy.png)

## Performance Mitigation Tactics

In order not to have overall performance constrained by memory, CPU designers had to employ mitigation tactics of:

+ [Memory caching](https://en.wikipedia.org/wiki/CPU_cache).
+ [Instruction parallelization](https://en.wikipedia.org/wiki/Instruction-level_parallelism).
+ [Speculative execution](https://en.wikipedia.org/wiki/Speculative_execution).
+ Multiple CPUs/cores.

All of these tactics are done entirely by the hardware. You as the programmer have no way either to know or really influence what’s going on under the hood.

Additionally, compiler implementors also employ their own mitigation tactics of:

+ [Constant folding](https://en.wikipedia.org/wiki/Constant_folding).
+ [Copy elision](https://en.wikipedia.org/wiki/Copy_elision).
+ [Statement hoisting](https://en.wikipedia.org/wiki/Loop-invariant_code_motion).
+ [Instruction scheduling](https://en.wikipedia.org/wiki/Instruction_scheduling).
+ [Loop unrolling](https://en.wikipedia.org/wiki/Loop_unrolling).
+ ... and many more.

The compiler is free to do any optimization so long as it makes no change to the _observable behavior_ of your program (the “[as-if rule](https://en.wikipedia.org/wiki/As-if_rule)”).

As long as your program has only a single thread, you can remain blissfully unaware of either the hardware or compiler tactics being employed. However, once you have multiple threads, you must become acutely aware of what’s going on under the hood.

## Atomic

When doing multithreaded programming, you’ll hear the term “atomic” used. What, exactly, is meant by “atomic” anyway? There are three related, but distinct, meanings:

1. A value operation (read or write) completes with no possible intervening operation by another thread, e.g., writing single-byte values on any CPU, or 16- or 32-bit values on a 32-bit CPU, or 64-bit values on a 64-bit CPU.

2. An updated value is visible to other CPUs.

3. Multiple value operations complete with no possible intervening operation by another thread, e.g., updating A and B _together_ (“transactional”).

“Atomic” always means #1; it usually also means #2; or all three.

## A (Bad) Example

Consider the following code where the main thread spawns another.  Both threads run so long as `shutdown` remains `false`. To shut down, the main thread sets `shutdown` to `true`. In response, both `while` loops will exit and the main thread will join the other thread. Unfortunately, the code is wrong.  (More unfortunately, I’ve seen such code in production.)

```cpp
bool shutdown;

void thread_1() {
    while ( !shutdown ) {
        // ...
    }
}

int main() {
    std::thread t1{ thread_1 };
    while ( !shutdown ) {
        // ...
        if ( some_condition )
            shutdown = true;
    }
    t1.join();
}
```

It’s wrong because `shutdown` is shared by multiple threads improperly.  Some programmers mistakenly think along the lines of:

> “It’s just a `bool`, a single byte, so of _course_ it’s thread-safe because you can’t read or write _half_ a byte, so it must be atomic.” 

The problem is that while that’s actually true, it’s insufficient.  A `bool` is atomic _only_ by meaning #1; it’s _not_ atomic by meaning #2. That is, just because a `bool` is updated by one thread does _not_ mean that updated value is _visible_ to other threads (running on other CPUs).

## A (Bad) Fix: `volatile`

I’ve also seen code where programmers knew they had to do something more to make such code thread-safe.  Unfortunately, that something turned out to be:

```cpp
volatile bool shutdown;  // Thread-safe now?  No!
```

That is, they inserted `volatile` because they kind-of understand what it does, but not what it’s _for_. The attempted use of `volatile` to make something thread-safe is _always_ wrong in C++.

> To understand what `volatile` does and what it’s for, see [here](https://dev.to/pauljlucas/what-volatile-does-in-c-and-c-5147).

## A Better Fix: Mutexes & Locks

The classic way to fix this code (correctly) would be to use a [mutex](https://en.cppreference.com/w/cpp/thread/mutex):

```cpp
bool shutdown;
std::mutex shutdown_mux;

void thread_1() {
    while ( true ) {
        // ...
        std::lock_guard<std::mutex> lock{ shutdown_mux };
        if ( shutdown )
            break;
    }
}

int main() {
    std::thread t1{ thread_1 };
    while ( true ) {
        // ...
        if ( some_condition ) {
            std::lock_guard<std::mutex> lock{ shutdown_mux };
            shutdown = true;
            break;
        }
    }
    t1.join();
}
```

The mutexes and locks make `shutdown` be atomic by meaning #1 **_and_** meaning #2.  While not necessary for this program, mutexes and locks also make things atomic by meaning #3 as well, so they’re the most general, one-size-fits-all tool for making programs thread-safe. However, C++ offers alternative tools that provide a more custom fit especially useful in high-performance code.

## A Word of Caution

Writing safe multithreaded code even with ordinary mutexes and locks is _hard_ to get right, [even for experts](https://arstechnica.com/information-technology/2014/05/linux-gets-fix-for-code-execution-flaw-that-went-unpatched-since-2009/).  Writing safe multithreaded code using advanced thread-safety techniques is _even harder_! Before considering them, you should:

+ Know that using efficient algorithms matters _far_ more than locking technique.  For example, an N&sdot;log(N) algorithm with slower mutexes will still very likely be more performant than an N<sup>2</sup> algorithm with faster locking (or lock-free) techniques.

+ **_Measure_** to see if your code is spending too much time locking.  (Remember: results are CPU-dependent!)

+ **_Only_** if locking takes a significant percentage of time, then consider the following techniques.

## An Even Better Fix: `std::atomic`

While use of mutexes and locks is correct, they’re fairly heavy-weight. In the case of using a `bool`, a much lighter-weight fix is:

```cpp
std::atomic<bool> shutdown;  // Thread-safe now?  Yes!
```

Use of [`std::atomic<T>`](https://en.cppreference.com/w/cpp/atomic/atomic) does _not_ make `shutdown` atomic by meaning #1 (it already is); it makes it atomic by meaning #2.

The `std::atomic<T>` class is specialized for all built-in types (`bool`, `char`, `int`, etc.) and all pointer types (`T*` for any `T`). It can even be used for your own type `T`, but _only_ when:

1. `T` is _trivially copyable_ (that is, if [`memcpy()`](https://en.cppreference.com/w/cpp/string/byte/memcpy) would correctly copy `T`).
2. `sizeof(T)` &le; 16 (typically).

When `T` is an integral or pointer type, `std::atomic<T>` has conventional operators overloaded for it:

```cpp
std::atomic<int> x{ 0 };

x = 1;      // x.store(1)
int i = x;  // x.load()
++x;        // x.fetch_add(1)
x++;        // x.fetch_add(1)
--x;        // x.fetch_sub(1)
x--;        // x.fetch_sub(1)
x += 1;     // x.fetch_add(1)
x -= 1;     // x.fetch_sub(1)
x &= 1;     // x.fetch_and(1)
x |= 1;     // x.fetch_or(1)
x ^= 1;     // x.fetch_xor(1)
```

The operators are shorthands for the member functions shown in the comments.  While the operators are convenient, I always use the member functions to make it obvious in code that the variable being manipulated is a `std::atomic`.

Incidentally, this:

```cpp
x = x + 1;  // not the same as either ++x or x += 1
```

is [not thread-safe](https://godbolt.org/z/Y8a6zPKz3) because the read of `x` and the write to `x` are not atomic by meaning #3.

## Lock-Free Atomics

Even though `std::atomic<T>` offers better performance over mutexes and locks, it’s not _guaranteed_ to.  For a type `T` on a _specific_ CPU under _specific_ conditions, [`is_lock_free()`](https://en.cppreference.com/w/cpp/atomic/atomic/is_lock_free) and [`is_always_lock_free()`](https://en.cppreference.com/w/cpp/atomic/atomic/is_always_lock_free) check.  Those conditions include:

+ Accessing unaligned values, e.g., reading an `int` at a memory address that’s not evenly divisible by `sizeof(int)` (assuming the CPU can even do it at all without generating a [bus error](https://en.wikipedia.org/wiki/Bus_error#Unaligned_access)).

+ Runtime CPU dispatching, e.g., a particular program during initialization may detect whether the CPU supports the `cmpxchg16b` instruction and, if not, may be forced to use locks.

The only type that’s _guaranteed_ to be always lock-free on all CPUs under all conditions is [`std::atomic_flag`](https://en.cppreference.com/w/cpp/atomic/atomic_flag) that’s a special-case of `std::atomic<bool>`.  (An example using `std::atomic_flag` is shown later.)

## Memory Barriers

Atomic (by any meaning) is _not_ enough to ensure thread-safety because the order of memory operations does not necessarily match the order of statements in a program. Why not? Because the hardware, the compiler, or both, may reorder things to improve performance. The “as-if” rule holds only from the perspective of a _single_ thread.

[Memory barriers](https://en.wikipedia.org/wiki/Memory_barrier) (aka, “fences”) help ensure thread-safety by selectively prohibiting reordering of memory operations across the barrier.  They also provide some synchronization among threads.  C++ provides [`std::memory_order`](https://en.cppreference.com/w/cpp/atomic/memory_order).

The sometimes confusing thing about memory barriers is that they’re about controlling the _order_ of operations, not the operations themselves.

### `memory_order_seq_cst`: Sequential Consistency

This is the safest memory order which is why it’s the default.  For example, the signature of `std::atomic<T>::fetch_add()` is:

```cpp
T fetch_add( T arg, std::memory_order order
                    = std::memory_order_seq_cst ) noexcept;
```

It’s also the least efficient because it establishes a _global_ memory ordering (bottleneck) across _all_ threads.  In specific cases, more efficient memory orders can be used.

### `memory_order_relaxed`: No Ordering

This is the least safe memory order in that it does _not_ guarantee operation order or synchronization, but still guarantees modification order.  What good is that?  A typical use-case is incrementing reference counts:

```cpp
template<typename T>
class shared_ptr {
public:
    // ...
private:
    struct counted_obj {
        // ...
        std::atomic<size_t> _count;
        T _obj;
    };

    counted_obj *const _co;

    void _inc_ref() noexcept {
        _co->_count.fetch_add( 1, std::memory_order_relaxed );
    }

    // ...
};
```

At this point, you might ask something along the lines of:

> “If there’s no synchronization, how can this possibly work?  Couldn’t thread 1 increment the value from N to N+1 _and_ thread 2 _also_ increment the old value from N to N+1?”

The answer is no for two reasons:

1. Each increment is _still_ atomic (by meanings #1 _and_ #2) so each thread always sees the latest value.  What `memory_order_relaxed` does is allow the hardware or the compiler to reorder _other_ operations having nothing to do with `_count` either before or after its increment to improve _overall_ performance, not the performance of `_count` specifically.

2. Because `_count` is part of a private data structure, it’s _guaranteed_ that no actions are ever conditionally taken by another thread based on its current value.  Said another way, when _only_ performing an increment and _not_ altering the control flow in any thread, then use of `memory_order_relaxed` is safe.

An example of when `memory_order_relaxed` is _not_ safe is when decrementing reference counts. (More later.)

Now that you hopefully understand `memory_order_relaxed`, you should _never_ use it _unless_ you can _prove_ your use of it is correct _and_ it actually significantly improves performance.  Correct use of `memory_order_relaxed` is _very hard_ to do.

### `memory_order_acquire` & `memory_order_release`

These memory orders are safer and always used in pairs:

+ `memory_order_release` (used with `store()`) is used to “publish” information: no accesses can be reordered after.

+ `memory_order_acquire` (used with `load()`) is used to “subscribe” to information: no accesses can be reordered before.

In this example, `shared_data` is shared among two threads and `data_ready` that acts as a [semaphore](https://en.wikipedia.org/wiki/Semaphore_(programming)):

```cpp
int shared_data;
std::atomic<int> data_ready{ 0 };

void producer() {
    shared_data = 42;
    data_ready.store( 1, std::memory_order_release );
}

void consumer() {
    while ( data_ready.load( std::memory_order_acquire ) == 0 )
        ;
    assert( shared_data == 42 );  // always true
}

int main() {
    std::thread t1{ producer };
    std::thread t2{ consumer };
    t1.join();
    t2.join();
}
```

+ The `producer` sets `shared_data` then signals that the data is ready (or “publishes” it). The write to `shared_data` “happens before” the write to `data_ready` because the use of `memory_order_release` _guarantees_ that the write to `shared_data` can _not_ be reordered after `data_ready`.

+ Meanwhile, the `consumer` [busy waits](https://en.wikipedia.org/wiki/Busy_waiting) for the signal on `data_ready`, then safely reads `shared_data`.  The read from `data_ready` “happens before” the read from `shared_data` because the use of `memory_order_acquire` _guarantees_ that the read from `shared_data` can _not_ be reordered before `data_ready`.

Things to note:

+ `shared_data` itself need not be atomic.  (This is particularly useful for data that can not be made atomic either because it’s too big or is not trivially copyable.)
+ You can set _any_ amount of data, then “publish” all of it simultaneously.

At this point, you might ask whether busy waiting is efficient.  In general, it’s efficient when the waits are short — shorter than the time it would take to lock and unlock a mutex.

A general [spinlock](https://en.wikipedia.org/wiki/Spinlock) (a kind of busy waiting) can be implemented using [`std::atomic_flag`](https://en.cppreference.com/w/cpp/atomic/atomic_flag):

```cpp
std::atomic_flag mutex = ATOMIC_FLAG_INIT;

class spin_lock {
public:
    explicit spin_lock( std::atomic_flag *mutex ) noexcept :
        _mutex{ mutex }
    {
        while ( !_mutex->test_and_set( std::memory_order_acquire ) )
           ;
    }
    ~spin_lock() noexcept {
        _mutex->clear( std::memory_order_release );
    }
private:
    std::atomic_flag *const _mutex;
};
```

### `memory_order_consume`

This memory order is a special case of `memory_order_acquire` that allows operations to be _dependency-ordered_ that can be more efficient on [weakly ordered CPUs](https://preshing.com/20120930/weak-vs-strong-memory-models/) (ARM, PowerPC; but not x86). From the earlier example:

```cpp
int shared_data;
std::atomic<int> data_ready{ 0 };
```

There’s no _actual_ dependency between `shared_data` and `data_ready` other than what’s in our minds — which the compiler has no way to know. To create an _actual_ dependency that the compiler can use to keep things in dependency order, we can instead do:

```cpp
std::atomic<int*> data_ready{ nullptr };
 
void producer() {
    static int shared_data;
    shared_data = 42;
    data_ready.store( &shared_data, std::memory_order_release );
}

void consumer() {
    while ( (data_ready.load( std::memory_order_consume )) == nullptr )
        ;
    assert( *data_ready == 42 );  // always true
}
```

Now, we’ve created an _actual_ dependency using a pointer and a pointed-to value in that the value of the pointer has to be loaded _before_ the pointer is dereferenced.  The compiler can preserve this order without using an additional and more expensive memory barrier.

### `memory_order_acq_rel`

This memory order is `memory_order_acquire` and `memory_order_release` combined into one used for [read-modify-write](https://en.wikipedia.org/wiki/Read–modify–write) operations: no accesses can be reordered before _or_ after.  A typical use-case is decrementing reference counts:

```cpp
template<typename T>
class shared_ptr {
public:
    // ...

    ~shared_ptr() noexcept {
        if ( _co->_count.fetch_sub( 1, std::memory_order_acq_rel ) == 1 )
            delete _co;
    }

    // ...
};
```

The reason `memory_order_relaxed` can’t be used here is because a use of the reference counted object in another thread could be reordered to be after the `delete` happens resulting in [undefined behavior](https://dev.to/pauljlucas/undefined-behavior-in-c-and-c-3a20).

## `std::atomic_thread_fence()`

Using `std::atomic` with `memory_order_relaxed` is atomic without a barrier; using [`std::atomic_thread_fence()`](https://en.cppreference.com/w/cpp/atomic/atomic_thread_fence) is a barrier without a specific atomic.  It’s useful if you want to update several atomic values together.  For example, instead of doing:

```cpp
atomic<int> x, y;
x.store( 1, std::memory_order_release );
y.store( 2, std::memory_order_release );
```

you can do:

```cpp
x.store( 1, std::memory_order_relaxed );
y.store( 2, std::memory_order_relaxed );
std::atomic_thread_fence( std::memory_order_release );
```

But there is another difference.  Given:

```cpp
std::atomic<int> sync{ 0 };
// (1) load & store operations
sync.store( 1, std::memory_order_release );
// (2) store operations
```

No operations in (1) will be reordered after the store-release of `sync` into (2); however, store operations in (2) _can_ be reordered before the release into (1).

`std::atomic_thread_fence()` imposes stronger ordering guarantees than an operation on an atomic with the same memory order.  Given:

```cpp
// (1) load & store operations
std::atomic_thread_fence( std::memory_order_release );
// (2) load operations
sync.store( 1, std::memory_order_relaxed );
// (3) store operations
```

No operations in (1) will be reordered after _all_ subsequent store operations into (3) and store operations in (3) can _not_ be reordered before the fence into (1).  However, since `memory_order_release` controls store operations only, load operations in (2) _can_ be reordered before the release into (1).

The rules for `memory_order_acquire` are similar except it controls load operations only and enforces ordering in the opposite direction. The differences are subtle.  In general, an acquire or release associated with a particular atomic is preferred.

## Compare-and-Swap (CAS)

[Compare-and-swap](https://en.wikipedia.org/wiki/Compare-and-swap) (CAS), as its name suggests, is both compare _and_ swap operations done together atomically (by all atomic meanings). Conceptually, it’s implemented as:

```cpp
template<typename T>
bool atomic<T>::compare_exchange( T &expected, T desired ) {
    if ( this->_value == expected ) {
        this->_value = desired;
        return true;
    }
    expected = this->_value;
    return false;
}
```

except done atomically.  The idea is that you check the value of an atomic variable and:

+ If it’s the value you expect (or hope for), then (and _only_ then) set it to a new desired value; or:
+ If it’s _not_ the value you expect (or hope for), it means some other thread changed the value, so do nothing.  You are free to reattempt setting the value.

There are actually [two flavors](https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange): `compare_exchange_weak()` and `compare_exchange_strong()`.  (More on the difference later.)

> I don’t know why the C++ committee named these functions with “compare exchange” instead of the conventional “compare and swap.”  I’ll continue to use the “CAS” abbreviation regardless.

For example, we can reimplement the previous `spin_lock` class using CAS:

```cpp
std::atomic<bool> mutex;

class spin_lock {
public:
    explicit spin_lock( std::atomic<bool> *mutex ) noexcept :
        _mutex{ mutex }
    {
        bool flag = false;
        while ( !_mutex->compare_exchange_weak( flag, true ) )
            flag = false;  // must reset
    }

    ~spin_lock() noexcept {
        _mutex->store( false );
    }

private:
    std::atomic<bool> *const _mutex;
};
```

Using CAS, we check the value of `_mutex`:

+ If it’s `false`, it means it’s currently unlocked, so set it to `true` to indicate it’s now locked and return `true`.

+ If it’s `true`, it means it’s currently locked (by another thread), so do _not_ set the value and return `false`.

    Note that in this case, the first parameter of `flag` is an in/out parameter and it’s set to the atomic’s current value (here, `true`) even though we don’t care.  This forces us to reset `flag` to `false` prior to another attempt.

### Lock-Free Operations

One of the primary use-cases for CAS is that it allows you to implement _lock-free_ operations on data structures.  For example, part of a lock-free `stack` implementation might be:

```cpp
template<typename T>
class stack {
public:
    struct node {
       node *_next;
       T _data;
       explicit node( T &&data ) : _data{ std::move( data ) } { }
    };

    void push( T &&data ) {
        node<T> *new_node = new node<T>{ std::move( data ) };
        new_node->_next = _head.load( std::memory_order_relaxed );
 
        while ( !_head.compare_exchange_weak(
            new_node->_next, new_node,
            std::memory_order_release,
            std::memory_order_relaxed ) );
    }

private:
    std::atomic<node<T>*> _head;
};
```

After a new node is created, we try to update `_head`:

+ If it’s still equal to `new_node->_next` (the original value of `_head`), update `_head` to point to `new_node` using the memory order specified by the third argument.

+ If it’s _not_ equal, it means another thread snuck in and updated `_head` to point to different new node, so do nothing and reattempt. (Note that `new_node->_next` has been updated to be the _new_ `_head` pointing to the different node using the memory order specified by the fourth argument.)

### `compare_exchange_weak()` vs `compare_exchange_strong()`

The existence of `compare_exchange_weak()` implies there’s a `compare_exchange_strong()` — and there is.  The difference between them is:

+ `compare_exchange_strong()` fails (returns `false`) _only_ if the current value is not the expected value.

+ `compare_exchange_weak()` _may_ also fail if there’s a “spurious failure.”

A “spurious failure” is quirk on weakly ordered CPUs (e.g., ARM and PowerPC; but not x86) where the operation fails for reasons _other_ than the value not being the expected value.

So if `compare_exchange_strong()` never fails spuriously, why does `compare_exchange_weak()` exist?  Before answering that question, let’s look at a conceptual implementation of them both:

```cpp
enum class cas_result {
    EQUAL,
    NOT_EQUAL,
    SPURIOUS_FAILURE
};

template<typename T>
cas_result cas_weak_impl( atomic<T> *p, T &expected, T desired );

template<typename T> 
bool atomic<T>::compare_exchange_weak( T &expected, T desired ) {
    return cas_weak_impl( this, expected, desired ) == cas_result::EQUAL;
}

template<typename T>
bool atomic<T>::compare_exchange_strong( T &expected, T desired ) {
    cas_result cr;
    do {
        cr = cas_weak_impl( this, expected, desired );
    } while ( cr == cas_result::SPURIOUS_FAILURE );
    return cr == cas_result::EQUAL;
}
```

Assume there’s only `cas_weak_impl()` that implements a weak version of CAS:

+ `compare_exchange_weak()` is a simple wrapper around `cas_weak_impl()`.

+ `compare_exchange_strong()`, however, wraps it with a loop that effectively filters out spurious failures. The important thing to remember here is that there’s a loop.

Given that, the benefits of `compare_exchange_weak()` are:

1. Spurious failures tend not to happen all _that_ often.

2. When _your_ code is using a loop anyway, the weak version will yield better performance on weakly ordered CPUs (ARM, PowerPC; but not x86 — but it’s no worse).

3. Detects the _ABA Problem_ (on weak CPUs) — more later.

So then why does `compare_exchange_strong()` exist?

+ If you have a loop _only_ to filter out spurious failures, don’t: use `compare_exchange_strong()`.

+ But if you have a loop anyway, use `compare_exchange_weak()`.

+ However, if handling a spurious failure is expensive (for example, if you have to discard and reconstruct a new object), use `compare_exchange_strong()`.

+ But `compare_exchange_strong()` doesn’t detect the _ABA Problem_ (more later).

Given all that, you might wonder when would you ever _not_ have a loop for `compare_exchange_strong()`?  One example is implementing `try_lock()`:

```cpp
bool my_try_lock( std::atomic<bool> *mutex ) noexcept {
    bool flag = false;
    return mutex->compare_exchange_strong( flag, true );
}
```

## The “ABA Problem”

The [ABA Problem](https://en.wikipedia.org/wiki/ABA_problem) can be illustrated as follows.  Suppose thread 1 performs the following steps:

1. Read a memory location (value is “A”).
2. Do some work.
3. Read the same memory location again (value is still “A”).
4. Compare the original and recent values (they’re equal).
5. Conclusion: nothing has changed.

The problem is suppose thread 2 performs the following steps _while_ thread 1 is doing its step 2:

1. Write “B” to the same memory location.
2. Do some work.
3. Write “A” to the same memory location.

By the time thread 1 does its step 3, it reads “A” and believes nothing has changed — even though it has.  You might now ask:

> “If the value of “A” is the same, why does it matter?”

The answer is: sometimes it doesn’t — but sometimes it _does_.

Consider the `stack<T>::push()` code from earlier (repeated here for convenience):

```cpp
void push( T &&data ) {
    node<T> *new_node = new node<T>{ std::move( data ) };
    new_node->_next = _head.load( std::memory_order_relaxed );
 
    while ( !_head.compare_exchange_weak(
                new_node->_next, new_node,
                std::memory_order_release,
                std::memory_order_relaxed ) );
}
```

and the following illustration:

![ABA push](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/knzg5upro5oztny3qs4t.png)

State (1) shows the initial conditions where **A** and **B** are nodes on the stack, `_head` (**H**) points to **A**, and `new_node` (**N**) has its `_next` also point to **A**.  The dotted box contains `_head` and `new_node->_next` that are being compared. State (3) shows the desired final state where `_head` points to `new_node` and `new_node->_next` points to **A**.

But what if another thread sneaks in before the `while` loop is entered, pushes a new node **X** shown by state (2), then immediately pops it?  Both `_head` and `new_node->_next` still point to **A**, so `_head` will be set to `new_node` — which is correct. In this case, the ABA Problem isn’t actually a problem.

But now consider what the code for `stack<T>::pop()` might be:

```cpp
    T pop() {
        node<T> *first = _head.load( std::memory_order_relaxed );

        while ( first != nullptr &&
                !_head.compare_exchange_weak(
                    first, first->_next,
                    std::memory_order_release,
                    std::memory_order_relaxed ) );

        if ( first == nullptr )
            throw empty_stack_exception{};
        T ret_val{ std::move( first->_data ) };
        delete first;
        return ret_val;
    }
```

and the following illustration:

![ABA pop](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/84j33umdgcjvl4wkmb4l.png)

State (1) shows the initial conditions where **A**, **B**, and **C** are nodes on the stack and `_head` (**H**) and `first` (**F**) both point to **A**.  The dotted box contains `_head` and `first` that are being compared. State (5) shows the desired final state where `_head` points to **B**.

But what if another thread sneaks in before the `while` loop is entered, pops **A** and **B** shown by state (2), then pushes **A** shown by state (3)?  Both `_head` and `first` still point to **A**, so `_head` will be set to `first->_next` — which is _wrong_!  Why?  Originally, `first` pointed to **A** whose `_next` pointed to **B**, hence `first->_next` (the desired argument in the compare) is **B**. But **B** was deleted in (2) so we’ll end up in state (4) with `_head` being a dangling pointer to **B** that was deleted. In this case, the ABA Problem _is_ actually a problem!  (It wasn’t a problem for `push()` because the desired value of `new_node` could never become stale.)

Even worse, there’s no easy fix for this.  In this case, the problem is that part of the desired value expression can change.  While `first` stays the same, what `first->_next` points to can change.  Detecting ABA Problems is _hard_, even for experts.

How can this be fixed?

1. Give up and just use a mutex and locks.
2. Implement _versioned pointers_.
3. Implement [hazard pointers](https://www.drdobbs.com/lock-free-data-structures-with-hazard-po/184401890).

## Versioned Pointers

A _versioned pointer_ is an ordinary pointer _plus_ an additional “version number” such that every time the value of the pointer changes, the version number is incremented.  Conceptually, something like:

```cpp
template<typename T>
class vers_ptr {
public:
    vers_ptr() noexcept : _ptr{ nullptr }, _vers{ 0 } { }
    vers_ptr( T *ptr ) noexcept : _ptr{ ptr }, _vers{ 1 } { }

    vers_ptr& operator=( T *ptr ) noexcept {
        set( ptr );
        return *this;
    }

    // ...

private:
    T *_ptr;
    uintptr_t _vers;  // must be sizeof(T*) for cmpxchg16b

    void set( T *ptr ) noexcept {
        _ptr = ptr;
        ++_vers;
    }
};

static_assert( sizeof( vers_ptr<void> ) == 16 );
```

Then use `vers_ptr<node>` instead of `node<T*>`:

```cpp
    struct node {
        vers_ptr<node> _next;
        // ...
    };

    T pop() {
        vers_ptr<node> first = _head.load( std::memory_order_relaxed );

        while ( first != nullptr &&
                !_head.compare_exchange_weak(
                    first, first->_next,
                    std::memory_order_release,
                    std::memory_order_relaxed ) ) ;
        // ...
    }

    // ...

    std::atomic<vers_ptr<node>> _head;
```

This would work because, even though the `_ptr` part of `first` would still point to **A**, its `_vers` part would be different, so `_head` and `first` would _not_ compare equal, so `_head` would _not_ be set to **B**, the stale value of `first->_next`.

The caveats of `vers_ptr`, however, are:

+ This will work only if the CPU supports double-pointer-wide (16 bytes on a 64-bit CPU) CAS (which, for example, x86_64 does via the `cmpxchg16b` instruction).

+ As mentioned, a specialization of `std::atomic<T>` requires `T` to be trivially copyable — which is why `operator=(vers_ptr<T> const&)` can’t be implemented.

## Cache Lines

For many CPUs, the L1 cache is “chunked” into [cache lines](https://en.wikipedia.org/wiki/CPU_cache#Cache_entries) typically ranging from 16-64K in size each.  To read a given memory location from main memory into the cache, the location _and_ the surrounding chunk-sized bytes are all read in together.  Similarly, to write a given memory location from the cache into main memory, the entire cache line is written.  For code that exhibits [locality of reference](https://en.wikipedia.org/wiki/Locality_of_reference), the chunking yields a performance gain.  However, in some cases, it can yield a performance loss.

Consider a lock-free `queue`:

```cpp
template<typename T>
class queue {
    // ...

    std::atomic<node*> _head;
    std::atomic<node*> _tail;
};
```

Assume that your code has one thread pushing items onto the tail of the queue (repeatedly updating `_tail`) and a second thread popping items from the head of the queue (repeatedly updating `_head`).

In the code as given, `_head` and `_tail` will very likely reside on the _same_ cache line.  This means updating one will invalidate the _entire_ cache line adding otherwise unnecessary contention for the other.

In a case such as this, you want `_head` and `_tail` to reside on _different_ cache lines so updating one doesn’t affect the other.  You can actually achieve that by using [`alignas`](https://en.cppreference.com/w/cpp/language/alignas) and [`hardware_destructive_interference_size`](https://en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size):

```cpp
template<typename T>
class queue {
    // ...
    alignas(std::hardware_destructive_interference_size) std::atomic<node*> _head;
    alignas(std::hardware_destructive_interference_size) std::atomic<node*> _tail;
};
```

This will waste a little bit of memory, but ensure that `_head` and `_tail` reside on different cache lines.

## Conclusion

To summarize:

+ Your algorithm matters _far_ more than locking technique.

+ Thread-safety in general and using atomics and barriers directly specifically is _very_ hard to get right, even for experts.

+ Before using advanced thread-safety techniques, measure to see if your code is spending too much time locking. (Remember: results are CPU-dependent!)

+ Only if locking takes a significant percentage of time, then consider atomics and barriers.

+ Atomics and barriers are two sides of the same coin.

+ Compare-and-swap (CAS) is a fundamental building-block.

+ Be aware of the ABA Problem.

+ Be aware of cache lines.