CAS Loops: The Heart of Atomic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <atomic>
 
std::atomic<int> counter{0};
 
// Pattern 1: Simple update (increment by delta)
void add_to_counter(int delta) {
    int old_value = counter.load(std::memory_order_relaxed);
    
    // When using compare_exchange_weak:
    // - 'old_value' is updated to actual value on failure
    // - This means we don't need to call load() again!
    while (!counter.compare_exchange_weak(
        old_value,                        // Expected (updated on failure)
        old_value + delta,                // Desired
        std::memory_order_release,        // Success ordering
        std::memory_order_relaxed         // Failure ordering
    )) {
        // On failure, old_value now contains current value
        // Loop naturally retries with correct expected value
    }
}
 
// Pattern 2: Conditional update (only if condition met)
bool increment_if_below_max(int max_value) {
    int old_value = counter.load(std::memory_order_relaxed);
    
    while (old_value < max_value) {       // Check condition
        int new_value = old_value + 1;
        
        if (counter.compare_exchange_weak(
            old_value, new_value,
            std::memory_order_release,
            std::memory_order_relaxed
        )) {
            return true;                   // Successfully incremented
        }
        // old_value updated to current; loop rechecks condition
    }
    
    return false;                          // max_value reached
}
 
// Pattern 3: State transition (from specific state to another)
enum State { IDLE, RUNNING, STOPPED };
std::atomic<State> state{IDLE};
 
bool try_start() {
    State expected = IDLE;                 // Only start from IDLE
    
    // Here we use compare_exchange_strong because:
    // - We only want ONE attempt from this specific state
    // - If we're not IDLE, we don't want to retry (return false)
    return state.compare_exchange_strong(
        expected, RUNNING,
        std::memory_order_acq_rel
    );
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <atomic>
 
std::atomic<int> counter{0};
std::atomic<bool> flag{false};
 
// ═══════════════════════════════════════════════════════════════
// GOOD: Use 'weak' in a retry loop
// ═══════════════════════════════════════════════════════════════
void increment_counter() {
    int expected = counter.load();
    // Weak is fine here - we're in a loop that retries anyway
    while (!counter.compare_exchange_weak(expected, expected + 1)) {
        // Spurious failure? Just retry. Same cost.
    }
}
 
// ═══════════════════════════════════════════════════════════════
// GOOD: Use 'strong' for single attempt / state transition
// ═══════════════════════════════════════════════════════════════
bool try_set_flag() {
    bool expected = false;
    // Strong because: if it fails, we want to know it REALLY failed
    // (i.e., flag was already set by someone else)
    return flag.compare_exchange_strong(expected, true);
}
 
// ═══════════════════════════════════════════════════════════════
// CAREFUL: Conditional loop with side effects
// ═══════════════════════════════════════════════════════════════
std::atomic<int*> global_ptr{nullptr};
 
bool try_install_pointer(int* new_ptr) {
    int* expected = nullptr;
    
    // Using 'weak' here is RISKY if there are side effects
    // Suppose: if we fail, we free new_ptr
    
    // WRONG with weak:
    // if (!global_ptr.compare_exchange_weak(expected, new_ptr)) {
    //     free(new_ptr);  // BUG: might free even though install succeeded!
    //     return false;
    // }
    
    // CORRECT: use strong when failure semantics matter
    if (!global_ptr.compare_exchange_strong(expected, new_ptr)) {
        free(new_ptr);     // Really failed - safe to free
        return false;
    }
    return true;
}
 
// ═══════════════════════════════════════════════════════════════
// ALSO OK: weak in conditional loop if failure is re-checked
// ═══════════════════════════════════════════════════════════════
bool increment_if_positive() {
    int expected = counter.load();
    
    while (expected > 0) {  // Re-check condition on each iteration
        // Weak is OK: spurious failure -> rechecks condition with new value
        if (counter.compare_exchange_weak(expected, expected + 1)) {
            return true;
        }
        // expected updated to current value; loop condition revalidates
    }
    return false;  // counter is non-positive
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include <atomic>
#include <chrono>
#include <thread>
#include <random>
 
std::atomic<int> counter{0};
 
// ═══════════════════════════════════════════════════════════════
// Strategy 1: Exponential Backoff
// ═══════════════════════════════════════════════════════════════
void increment_with_exponential_backoff() {
    constexpr int MIN_BACKOFF = 1;
    constexpr int MAX_BACKOFF = 1024;
    
    int backoff = MIN_BACKOFF;
    int expected = counter.load(std::memory_order_relaxed);
    
    while (!counter.compare_exchange_weak(
        expected, expected + 1,
        std::memory_order_release,
        std::memory_order_relaxed
    )) {
        // Backoff: spin for 'backoff' iterations
        for (int i = 0; i < backoff; ++i) {
            __builtin_ia32_pause();  // x86 PAUSE to reduce power & pipeline stalls
        }
        
        // Exponential increase with jitter
        backoff = std::min(backoff * 2, MAX_BACKOFF);
    }
}
 
// ═══════════════════════════════════════════════════════════════
// Strategy 2: Randomized Backoff
// ═══════════════════════════════════════════════════════════════
thread_local std::mt19937 rng(std::random_device{}());
 
void increment_with_random_backoff() {
    constexpr int MAX_BACKOFF = 512;
    
    int backoff = 16;
    int expected = counter.load(std::memory_order_relaxed);
    
    while (!counter.compare_exchange_weak(
        expected, expected + 1,
        std::memory_order_release,
        std::memory_order_relaxed
    )) {
        // Random delay to desynchronize retry attempts
        std::uniform_int_distribution<int> dist(0, backoff - 1);
        int delay = dist(rng);
        
        for (int i = 0; i < delay; ++i) {
            __builtin_ia32_pause();
        }
        
        // Increase range for next failure
        backoff = std::min(backoff * 2, MAX_BACKOFF);
    }
}
 
// ═══════════════════════════════════════════════════════════════
// Strategy 3: Yielding Backoff (for long contention)
// ═══════════════════════════════════════════════════════════════
void increment_with_yield_backoff() {
    int spin_count = 0;
    constexpr int SPINS_BEFORE_YIELD = 100;
    
    int expected = counter.load(std::memory_order_relaxed);
    
    while (!counter.compare_exchange_weak(
        expected, expected + 1,
        std::memory_order_release,
        std::memory_order_relaxed
    )) {
        ++spin_count;
        
        if (spin_count < SPINS_BEFORE_YIELD) {
            // First few attempts: just pause
            __builtin_ia32_pause();
        } else {
            // Many failures: yield CPU to other threads
            std::this_thread::yield();
            spin_count = 0;  // Reset counter after yield
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

#include <atomic>
 
std::atomic<int> counter{0};
std::atomic<int*> ptr{nullptr};
 
// ═══════════════════════════════════════════════════════════════
// BUG 1: Ignoring CAS result
// ═══════════════════════════════════════════════════════════════
void wrong_increment() {
    int old_val = counter.load();
    int new_val = old_val + 1;
    
    // BUG: CAS might fail if another thread updated counter!
    counter.compare_exchange_strong(old_val, new_val);
    // We proceed as if it succeeded, but it might not have!
}
 
void correct_increment() {
    int old_val = counter.load();
    while (!counter.compare_exchange_weak(old_val, old_val + 1)) {
        // Retry loop handles failures
    }
}
 
// ═══════════════════════════════════════════════════════════════
// BUG 2: Reloading after CAS failure
// ═══════════════════════════════════════════════════════════════
void wrong_reload() {
    int old_val = counter.load();
    
    while (!counter.compare_exchange_weak(old_val, old_val + 1)) {
        old_val = counter.load();  // BUG: Unnecessary reload!
        // compare_exchange already updated old_val on failure
        // This load might get a DIFFERENT value than what CAS saw
    }
}
 
void correct_no_reload() {
    int old_val = counter.load();
    
    while (!counter.compare_exchange_weak(old_val, old_val + 1)) {
        // old_val was already updated to current value by failed CAS
        // No reload needed!
    }
}
 
// ═══════════════════════════════════════════════════════════════
// BUG 3: Not updating expected in conditional loop
// ═══════════════════════════════════════════════════════════════
bool wrong_conditional() {
    int old_val = counter.load();
    
    while (old_val < 100) {
        if (counter.compare_exchange_weak(old_val, old_val + 1)) {
            return true;
        }
        // BUG: If condition used 'old_val' but we reload separately:
        old_val = counter.load();  // Wait, this is what we checked above
        // Actually this is borderline - the real bug is when you DON'T
        // update old_val at all between loop iterations
    }
    return false;
}
 
// ═══════════════════════════════════════════════════════════════
// BUG 4: Missing memory ordering
// ═══════════════════════════════════════════════════════════════
std::atomic<bool> ready{false};
int data = 0;
 
void wrong_ordering() {
    data = 42;
    
    // BUG: relaxed ordering doesn't guarantee 'data' write is visible
    // before 'ready' write is seen by other threads
    ready.store(true, std::memory_order_relaxed);  // BUG!
}
 
void correct_ordering() {
    data = 42;
    
    // release ensures all prior writes (including 'data') are visible
    // to threads that see ready==true with acquire semantics
    ready.store(true, std::memory_order_release);  // Correct!
}
 
// ═══════════════════════════════════════════════════════════════
// BUG 5: Using local variable after CAS (stale reference)
// ═══════════════════════════════════════════════════════════════
struct Node { int value; Node* next; };
std::atomic<Node*> head{nullptr};
 
void wrong_stale_reference() {
    Node* old_head = head.load();
    
    if (old_head == nullptr) return;
    
    Node* new_head = old_head->next;
    
    if (head.compare_exchange_strong(old_head, new_head)) {
        int value = old_head->value;  // BUG: old_head might be freed!
        // Another thread could have also popped and freed this node
        // Use-after-free hazard!
    }
}
 
// Solution: use hazard pointers, epoch-based reclamation, etc.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <atomic>
 
std::atomic<bool> lock{false};
std::atomic<int> counter{0};
 
// ═══════════════════════════════════════════════════════════════
// Optimization 1: Read before writing (TTAS pattern)
// ═══════════════════════════════════════════════════════════════
void acquire_lock_ttas() {
    while (true) {
        // READ first (cheap, can use shared cache line)
        while (lock.load(std::memory_order_relaxed)) {
            __builtin_ia32_pause();
        }
        
        // Now try CAS (expensive, requires exclusive cache line)
        bool expected = false;
        if (lock.compare_exchange_weak(
            expected, true,
            std::memory_order_acquire,
            std::memory_order_relaxed
        )) {
            return;  // Got it!
        }
        // Someone else grabbed it first, back to reading
    }
}
 
// ═══════════════════════════════════════════════════════════════
// Optimization 2: Hoisting invariant checks out of loop
// ═══════════════════════════════════════════════════════════════
std::atomic<int> bounded_counter{0};
constexpr int MAX_VALUE = 100;
 
bool increment_bounded_optimized() {
    int expected = bounded_counter.load(std::memory_order_relaxed);
    
    // Check termination condition ONCE before potentially expensive loop
    if (expected >= MAX_VALUE) {
        return false;  // Fast path: already at max
    }
    
    do {
        if (expected >= MAX_VALUE) {
            return false;  // Rechecked condition after failure
        }
    } while (!bounded_counter.compare_exchange_weak(
        expected, expected + 1,
        std::memory_order_release,
        std::memory_order_relaxed
    ));
    
    return true;
}
 
// ═══════════════════════════════════════════════════════════════
// Optimization 3: Batching operations to reduce contention
// ═══════════════════════════════════════════════════════════════
std::atomic<int> shared_counter{0};
thread_local int local_count = 0;
 
void increment_batched() {
    // Accumulate locally
    local_count++;
    
    // Flush to shared counter periodically
    if (local_count >= 100) {
        int old = shared_counter.load(std::memory_order_relaxed);
        while (!shared_counter.compare_exchange_weak(
            old, old + local_count,
            std::memory_order_release,
            std::memory_order_relaxed
        )) {}
        local_count = 0;
    }
}
 
int get_total() {
    // Note: reading from all thread-local counts would be needed
    // for exact count; shared_counter is approximate
    return shared_counter.load(std::memory_order_acquire);
}
 
// ═══════════════════════════════════════════════════════════════
// Optimization 4: Using fetch_add when applicable
// ═══════════════════════════════════════════════════════════════
void increment_simple() {
    // For simple increment, fetch_add is more efficient than CAS loop
    // Hardware can optimize fetch_add better than repeated CAS
    counter.fetch_add(1, std::memory_order_relaxed);
}
 
// CAS loop only needed when:
// - Update depends on current value in complex way
// - Conditional update required
// - Multiple fields must change atomically (via pointer swap)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

#include <atomic>
#include <memory>
 
// ═══════════════════════════════════════════════════════════════
// Approach 1: CAS on pointer to immutable structure
// ═══════════════════════════════════════════════════════════════
struct Config {
    int timeout;
    int max_retries;
    std::string endpoint;
    
    // Config is immutable after construction
    // (no setters, all members const or effectively so)
};
 
std::atomic<Config*> current_config{nullptr};
 
void update_config(int new_timeout) {
    Config* old_config = current_config.load(std::memory_order_acquire);
    
    while (true) {
        // Create new immutable config
        Config* new_config = new Config{
            new_timeout,
            old_config ? old_config->max_retries : 3,
            old_config ? old_config->endpoint : "default"
        };
        
        // CAS the pointer
        if (current_config.compare_exchange_weak(
            old_config, new_config,
            std::memory_order_release,
            std::memory_order_acquire
        )) {
            // Success! Old config must be reclaimed safely
            // (using hazard pointers, RCU, etc.)
            schedule_reclamation(old_config);
            return;
        }
        
        // Failed - old_config now points to current config
        delete new_config;  // Discard our attempt
        // Loop retries with new old_config value
    }
}
 
// Readers get consistent snapshot automatically
Config* get_config() {
    return current_config.load(std::memory_order_acquire);
}
 
// ═══════════════════════════════════════════════════════════════
// Approach 2: Pack multiple values into one word
// ═══════════════════════════════════════════════════════════════
struct PackedState {
    uint32_t counter : 16;    // 16 bits
    uint32_t flags : 8;       // 8 bits
    uint32_t version : 8;     // 8 bits (for ABA prevention)
};
 
static_assert(sizeof(PackedState) == sizeof(uint32_t));
 
std::atomic<uint32_t> packed_state{0};
 
void increment_with_flags(uint8_t new_flags) {
    PackedState old_state, new_state;
    
    // Load as integer, interpret as packed struct
    uint32_t old_val = packed_state.load(std::memory_order_relaxed);
    
    do {
        old_state = *reinterpret_cast<PackedState*>(&old_val);
        
        new_state.counter = old_state.counter + 1;
        new_state.flags = new_flags;
        new_state.version = old_state.version + 1;
        
        uint32_t new_val = *reinterpret_cast<uint32_t*>(&new_state);
        
        if (packed_state.compare_exchange_weak(
            old_val, new_val,
            std::memory_order_acq_rel
        )) {
            return;
        }
        // old_val updated to current value
    } while (true);
}
 
// ═══════════════════════════════════════════════════════════════
// Approach 3: Double-width CAS (DCAS / CMPXCHG16B)
// ═══════════════════════════════════════════════════════════════
struct alignas(16) DoubleWord {
    void* ptr;
    uint64_t tag;
};
 
std::atomic<DoubleWord> tagged_ptr;
 
bool cas_tagged_ptr(void* expected_ptr, uint64_t expected_tag,
                    void* new_ptr, uint64_t new_tag) {
    DoubleWord expected{expected_ptr, expected_tag};
    DoubleWord desired{new_ptr, new_tag};
    
    return tagged_ptr.compare_exchange_strong(expected, desired);
}
 
// Note: Requires 16-byte aligned storage and CMPXCHG16B support
// C++ std::atomic<DoubleWord> should handle this on x86-64

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <atomic>
#include <cassert>
#include <iostream>
 
std::atomic<int> counter{0};
 
// ═══════════════════════════════════════════════════════════════
// Defensive CAS loop with debugging support
// ═══════════════════════════════════════════════════════════════
void increment_defensive() {
    int attempts = 0;
    constexpr int MAX_ATTEMPTS = 1000000;
    
    int expected = counter.load(std::memory_order_relaxed);
    
    while (!counter.compare_exchange_weak(
        expected, expected + 1,
        std::memory_order_release,
        std::memory_order_relaxed
    )) {
        attempts++;
        
        // Detect potential livelock / extreme contention
        if (attempts > MAX_ATTEMPTS) {
            std::cerr << "WARNING: CAS loop exceeded " << MAX_ATTEMPTS 
                      << " attempts. Possible livelock." << std::endl;
            std::cerr << "Expected: " << expected 
                      << ", Current: " << counter.load() << std::endl;
            // In production: maybe switch to lock-based fallback
            assert(false && "CAS loop appears livelocked");
        }
        
        // Logging for debug analysis
        #ifdef DEBUG_CAS
        if (attempts % 100 == 0) {
            std::cerr << "CAS retry #" << attempts 
                      << ", expected=" << expected << std::endl;
        }
        #endif
    }
    
    // Post-condition: counter increased by exactly 1
    // (Hard to verify directly, but assertions on final state help)
}
 
// ═══════════════════════════════════════════════════════════════
// Invariant checking wrapper
// ═══════════════════════════════════════════════════════════════
class AtomicBoundedCounter {
    std::atomic<int> value_{0};
    int min_, max_;
    
public:
    AtomicBoundedCounter(int min, int max) : min_(min), max_(max) {}
    
    bool increment() {
        int expected = value_.load(std::memory_order_relaxed);
        
        while (expected < max_) {
            if (value_.compare_exchange_weak(
                expected, expected + 1,
                std::memory_order_release,
                std::memory_order_relaxed
            )) {
                // Assert invariant after successful modification
                int new_val = value_.load(std::memory_order_acquire);
                assert(new_val >= min_ && new_val <= max_ && 
                       "Invariant violated!");
                return true;
            }
        }
        return false;
    }
};