The CAS Succeeded on a Recycled Generation

The lock-free path failed on reuse, not enqueue. Pointer-only CAS cannot see a recycled node. I treat every successful compare_exchange as a suspect now.

The symptom that looked impossible

The consumer printed a value nobody had pushed. Logs showed a matching pointer value. The compare_exchange call had returned true.

So who wrote the garbage into that node? I reconstructed it in a tight recycle loop. Two worker threads were already enough here.

Did I need a big machine for this? No extra hardware made the race clearer. I needed a tiny pool and a stalled load.

What I thought the code guaranteed

I started from a Treiber-style stack in the lab. Pop swapped head from node A to node B. A later push recycled A back into that list.

A returned with a brand new next pointer. The stalled pop still compared against pointer A. That pointer comparison was the entire bug.

Here is the broken sketch I used. Treat it as a lab reconstruction only.

// reconstruction: pointer-only Treiber stack (broken under reuse)
#include <atomic>
#include <cstdint>

struct Node {
    std::atomic<Node*> next{nullptr};
    int value{0};
};

struct Stack {
    std::atomic<Node*> head{nullptr};

    void push(Node* n) {
        Node* h;
        do {
            h = head.load(std::memory_order_acquire);
            n->next.store(h, std::memory_order_relaxed);
        } while (!head.compare_exchange_weak(
            h, n,
            std::memory_order_release,
            std::memory_order_acquire));
    }

    Node* pop() {
        Node* h;
        Node* n;
        do {
            h = head.load(std::memory_order_acquire);
            if (!h) return nullptr;
            n = h->next.load(std::memory_order_acquire);
        } while (!head.compare_exchange_weak(
            h, n,
            std::memory_order_release,
            std::memory_order_acquire));
        return h;
    }
};

Looks textbook, right? It is textbook stack code. Textbook code assumes nodes never return from a pool.

The reuse pool that made it real

I did not malloc on every single push. I kept a free list for the datapath. That choice is normal. It is also how ABA becomes real.

The free list handed A back to a pusher. Pop still held A in a local. Identity matched. Contents did not.

Walk the race in order. Number it. Do not skip a step.

1. Thread T1 loads head A and next B.
2. Thread T2 pops A, then pops B after that.
3. Thread T2 pushes X, then recycles A as head.
4. Head is A again, but A's next is X.
5. T1 compare_exchange swaps head from A to B.
6. B is free or live elsewhere, so the stack is corrupt.

The CAS succeeded on the old pointer. The generation was already gone. Why did my first tests miss that race?

The tests that lied

Single-thread tests never recycle under a stalled load. Address sanitizer missed the bug too. ASan tracks use-after-free, not legal reuse.

My pool was not calling free at all. Poisoned malloc would not have helped here. I needed a reuse stress, not a quiz.

Here is the harness I run in the lab. It is a reconstruction, not a production trace.

// reconstruction: reuse stress against a bounded node pool
#include <atomic>
#include <cstdint>
#include <random>
#include <vector>

void recycle(std::vector<Node*>& free_list, Node* n) {
    n->value = 0x7F7F7F7F; // poison after pop
    free_list.push_back(n);
}

Node* lease(std::vector<Node*>& free_list) {
    if (free_list.empty()) return nullptr;
    Node* n = free_list.back();
    free_list.pop_back();
    return n;
}

void reuse_stress(Stack& s,
                  std::vector<Node*>& local_free,
                  std::atomic<bool>& stop) {
    std::mt19937 rng{std::random_device{}()};
    while (!stop.load(std::memory_order_relaxed)) {
        Node* n = lease(local_free);
        if (!n) {
            n = s.pop();
            if (!n) continue;
            recycle(local_free, n);
            continue;
        }
        n->value = static_cast<int>(rng() & 0x3fffffff);
        int published = n->value;
        s.push(n);
        Node* out = s.pop();
        if (!out) continue;
        // invariant: a recycled slot must not surface stale identity
        if (out->value == 0x7F7F7F7F) {
            std::abort(); // reconstruction tripwire
        }
        (void)published;
        recycle(local_free, out);
    }
}

Run several workers against one tiny pool. Keep the pool smaller than the thread count. That pressure forces the ABA window open.

Did your CI do that to lock-free code? Mine did not at first. Happy-path tests are a trap here.

Build lines I actually type for this reconstruction:

g++ -std=c++17 -O2 -pthread aba_repro.cpp -o aba_repro
./aba_repro
g++ -std=c++17 -O1 -g -fsanitize=thread -pthread aba_repro.cpp -o aba_tsan
./aba_tsan

Thread sanitizer can still miss ABA here. ABA is not a data race on paper. It is a logic race on node identity.

A second bug sitting on the same path

I also read the payload before the CAS succeeded. That is another defect. The slot can be recycled during that load.

Is the value field even stable then? No, not under a pool. I moved the payload copy to after a successful tagged CAS.

If you only fix ABA, you can still tear a payload. Stamp the identity first. Then copy the value out.

Where an assistant helped, and where it did not

I asked an assistant for a lock-free stack sketch. It emitted the pointer-only CAS above. It also emitted tidy happy-path tests.

Those tests compiled on the first try. They never reused a node under a stalled pop. They could not see the generation gap.

Disclosure: This article was prepared as part of MonkeyCode's product outreach.

I used MonkeyCode's free model access to draft candidates. I used the free server option to run the reuse harness. Neither step proved the CAS. The harness did.

Would I skip the assistant next time? No. I skip trusting its tests.

The tagged index fix

I needed identity plus generation in one CAS key. Packed pointers are cute and brittle. A pool index plus a stamp is clearer.

// reconstruction: index + generation CAS (pool-backed)
#include <atomic>
#include <cstdint>
#include <limits>
#include <vector>

struct Slot {
    std::atomic<uint32_t> next;
    int value;
};

struct Head {
    uint32_t idx;
    uint32_t gen;
};

constexpr uint32_t kNil = std::numeric_limits<uint32_t>::max();

struct TaggedStack {
    std::atomic<uint64_t> head;
    std::vector<Slot> slots;

    static uint64_t pack(Head h) {
        return (uint64_t(h.gen) << 32) | uint64_t(h.idx);
    }
    static Head unpack(uint64_t v) {
        return Head{uint32_t(v), uint32_t(v >> 32)};
    }

    explicit TaggedStack(std::size_t n) : slots(n) {
        head.store(pack(Head{kNil, 0}), std::memory_order_relaxed);
        for (auto& s : slots) s.next.store(kNil, std::memory_order_relaxed);
    }

    void push(uint32_t idx, int value) {
        slots[idx].value = value;
        uint64_t cur;
        do {
            cur = head.load(std::memory_order_acquire);
            Head h = unpack(cur);
            slots[idx].next.store(h.idx, std::memory_order_relaxed);
        } while (!head.compare_exchange_weak(
            cur, pack(Head{idx, unpack(cur).gen + 1}),
            std::memory_order_release,
            std::memory_order_acquire));
    }

    bool pop(int& out) {
        uint64_t cur;
        Head h;
        uint32_t nxt;
        do {
            cur = head.load(std::memory_order_acquire);
            h = unpack(cur);
            if (h.idx == kNil) return false;
            nxt = slots[h.idx].next.load(std::memory_order_acquire);
        } while (!head.compare_exchange_weak(
            cur, pack(Head{nxt, h.gen + 1}),
            std::memory_order_release,
            std::memory_order_acquire));
        out = slots[h.idx].value; // copy after the tagged CAS
        return true;
    }
};

The CAS key is now index and generation together. A recycled index fails the stamp. That is the entire fix in this lab.

Pop must bump generation too. Miss that bump and ABA returns. I missed it once in this reconstruction.

Do not copy the snippet blindly into a datapath. Wire pop, push, and recycle together. Then rerun the tiny pool until it holds.

Decision table I keep above the keyboard

If the pool never reuses, you will never see this. Lucky is not the same as correct.

Numbered debugging workflow I reuse

1. Freeze the node type and record index plus generation together.
2. Log CAS old and new packed words as one sample.
3. Force a tiny recycle pool, like four slots and eight threads.
4. Assert each pop value was published after the last recycle.
5. Histogram generations per index; a flat line means no stamp.
6. Only then change the algorithm under the same harness.

Skip step three and you will ship the textbook stack. I almost did that here.

Limitations

This tagged-index scheme needs a bounded pool. It does not replace a memory reclaimer. It does not prove linearizability for the stack.

It does not help if you CAS the wrong word. Epoch reclamation is a different tool. Hazard pointers are a different tool.

I did not implement those reclaimers here. An assistant will still emit pointer-only CAS. So will old blog posts on a tired night.

Who should not use this approach

Do not drop this into a packet path untested. Do not ship lock-free code from a unit test that never reuses. Do not pack pointers if your ABI allows non-canonical addresses.

If you can take a mutex, take a mutex. A latency budget is not a personality trait.

Students learning atomics should start with a mutexed stack. Then break it on purpose in a lab. Then add the stamp and the reuse harness.

What I will not claim

I will not quote a speedup from this note. I did not measure one for this reconstruction. I will not name models or invent a quota.

The lesson is smaller than a product pitch. A true CAS can still be wrong. Reuse is the missing test, not another happy path.

Stamp the identity or take a mutex. That is the whole retrospective.