The Tail Advanced Before the Bytes Did

Lock-free C++ can lie with green tests. I watched a ring buffer drop real payloads. The tail index moved before the bytes landed. One producer hid that race from every test. Do you still trust a single TSan run?

This is a lab retrospective, not a war story. I built a small SPSC ring. Then I let a model draft the atomics. The compile was clean. The unit tests were clean. Load was not.

What broke in the lab

The consumer printed garbage after a few million pushes. Sometimes it printed a stale struct. Sometimes it printed a half-updated id. Did the slot get overwritten? Or did the index leak early?

I had no production metrics to wave around. I had a repro and a failing assert. That was enough to start.

The code that looked finished

Here is the reduced producer path. Treat it as the broken lab copy.

// lab_repro: broken SPSC ring, C++20
#include <atomic>
#include <cstdint>
#include <vector>

struct Record {
  std::uint64_t id;
  std::uint64_t payload;
};

class BrokenRing {
 public:
  explicit BrokenRing(std::size_t cap)
      : cap_(cap), buf_(cap) {}

  bool push(Record r) {
    auto t = tail_.load(std::memory_order_relaxed);
    auto h = head_.load(std::memory_order_relaxed);
    if (t - h >= cap_) return false;
    buf_[t % cap_] = r;  // non-atomic payload write
    tail_.store(t + 1, std::memory_order_relaxed);  // leak
    return true;
  }

  bool pop(Record& out) {
    auto h = head_.load(std::memory_order_relaxed);
    auto t = tail_.load(std::memory_order_relaxed);
    if (h == t) return false;
    out = buf_[h % cap_];
    head_.store(h + 1, std::memory_order_relaxed);
    return true;
  }

 private:
  const std::size_t cap_;
  std::vector<Record> buf_;
  std::atomic<std::size_t> head_{0};
  std::atomic<std::size_t> tail_{0};
};

See the relaxed stores on both indexes? That is the whole trap. Why would a model pick relaxed? Because it compiles. Because x86 often forgives it.

Step 1: Freeze the symptom

I stopped changing the algorithm first. I only recorded failures. I logged id on push and id on pop. The sequences diverged under -O2.

Did debug mode still pass? Yes. Release did not. That split already screamed memory ordering. Have you seen that split before?

clang++ -std=c++20 -O0 -g ring_repro.cpp -o ring_o0
clang++ -std=c++20 -O2 -g ring_repro.cpp -o ring_o2
./ring_o0   # often quiet
./ring_o2   # garbage ids after load

Step 2: Shrink the surface

I removed logging from the hot path next. Logging itself can hide a race. I replaced it with a checksum in the record.

struct Record {
  std::uint64_t id;
  std::uint64_t payload;
  std::uint64_t checksum;
};

Record make(std::uint64_t id) {
  Record r{id, id ^ 0x9e3779b97f4a7c15ULL, 0};
  r.checksum = r.id ^ r.payload;
  return r;
}

bool valid(const Record& r) {
  return r.checksum == (r.id ^ r.payload);
}

The consumer then asserted valid(out). The assert died on the optimized binary. Was the slot reused too soon? Or was the write unpublished?

Step 3: Instrument the indexes

I sampled head and tail into a side log. I used a very large ring. Slot reuse became rare. The checksum still failed.

That killed the overwrite theory. The index was visible. The payload was not. Who published the tail too early?

// sampling only, never on the hot success path
if ((seen++ % 100000) == 0) {
  std::fprintf(stderr, "h=%zu t=%zu\n",
               head_.load(std::memory_order_relaxed),
               tail_.load(std::memory_order_relaxed));
}

Step 4: Ask for a patch, then distrust it

I wanted alternate memory-order patches quickly. I did not want another relaxed guess. Disclosure: This article was prepared as part of MonkeyCode's product outreach. I used MonkeyCode's free model access on the free server option to draft candidate diffs. I kept every diff out of the binary until the harness failed or passed on my machine.

The first draft still used relaxed loads on tail in pop. The second draft mixed acq_rel on one index only. Useful? As a checklist. Authoritative? No.

Would you merge a lock-free patch from a chat window? I would not.

Root cause

The producer wrote buf_[slot] as a plain store. Then it published tail with relaxed. A consumer can observe the new tail first. Then it reads a slot that has not landed. On x86 this is rarer. On weaker orders it is not theoretical.

memory_order_relaxed does not create a happens-before edge. The payload store is not ordered against the index store. The tests used one producer and almost no delay. So the race starved itself.

Is TSan a full memory-model oracle? No. ThreadSanitizer catches many races. It does not prove your orders on every CPU. A green TSan run is a filter. It is not a proof.

Memory-order decision table

Use this table before you touch another ring.

Operation	Wrong order I had	Order I required	Why
Producer payload write	plain store, unpublished	happens-before the tail store	Consumer must see bytes
Producer tail store	relaxed	release	Publishes prior writes
Consumer tail load	relaxed	acquire	Pairs with that release
Consumer payload read	plain load after acquire	stays plain	Ordered by the acquire
Consumer head store	relaxed	release	Publishes free slots
Producer head load	relaxed	acquire	Sees freed slots

If any row stays relaxed, stop. Ask why. Then write a test that can fail.

The fix I actually compiled

bool push(Record r) {
  auto t = tail_.load(std::memory_order_relaxed);
  auto h = head_.load(std::memory_order_acquire);
  if (t - h >= cap_) return false;
  buf_[t % cap_] = r;
  tail_.store(t + 1, std::memory_order_release);
  return true;
}

bool pop(Record& out) {
  auto h = head_.load(std::memory_order_relaxed);
  auto t = tail_.load(std::memory_order_acquire);
  if (h == t) return false;
  out = buf_[h % cap_];
  head_.store(h + 1, std::memory_order_release);
  return true;
}

The payload write now happens before a release store of tail. The consumer acquire-loads tail before it reads the slot. That is the pairing. Miss the pair and you are guessing.

This is still SPSC only. Two producers still make it wrong. I did not “fix” that with more relaxed atomics. I refused the MPSC version until the SPSC harness stayed clean.

The harness that would have caught it

Do not call this a benchmark. It is a fail-fast loop.

#include <thread>
#include <cassert>

int main() {
  BrokenRing q(1 << 12);
  constexpr int N = 2'000'000;
  std::thread prod([&] {
    for (int i = 1; i <= N; ++i) {
      Record r = make(static_cast<std::uint64_t>(i));
      while (!q.push(r)) std::this_thread::yield();
    }
  });
  std::thread cons([&] {
    Record out{};
    int seen = 0;
    while (seen < N) {
      if (!q.pop(out)) {
        std::this_thread::yield();
        continue;
      }
      assert(valid(out));
      assert(out.id == static_cast<std::uint64_t>(seen + 1));
      ++seen;
    }
  });
  prod.join();
  cons.join();
}

Build it two ways. Always.

clang++ -std=c++20 -O2 -fsanitize=thread -g harness.cpp -o harness_tsan
clang++ -std=c++20 -O2 -g harness.cpp -o harness_opt
./harness_tsan
./harness_opt

Run the optimized binary on a quiet machine and a busy machine. Yield is not a lock. It only changes timing. If the assert is timing-shaped, you do not have a fix.

What I refuse to claim

I have no model names to recite here. I have no quota numbers that I can defend today. I have no speedup chart. Those would be invented. The only claims I will keep are the ones in the harness.

Free model access can draft a diff. A free server option can host that draft loop. Neither one proves release and acquire pairing. Your CPU does. Your assert does.

Limitations

This pairing does not make the ring MPSC. It does not make it MPMC. % cap_ is also a footgun if cap_ is not stable. vector reallocation would be another bug. I never resize this buffer.

x86 may hide a broken relaxed version for days. ARM may not. TSan may stay quiet if the race is “only” a missing barrier. A model may reintroduce relaxed on the next refactor. Why would it not? Relaxed looks symmetric.

Who should skip this approach

Skip it if you cannot run a stress harness. Skip it if you need MPSC today. Skip it if you will paste atomics from a chat and ship. Skip it if your records are not trivially copyable. Skip it if you need wait-free progress proofs.

Use a mutex queue first if the rate is human. Lock-free is not a personality trait. It is a constraint you can measure.

What I keep doing

I start from the failing assert now. I do not start from a prettier atomic. I treat every relaxed as guilty. I pair release with acquire in a table. I run TSan and an optimized harness. I ask a model for diffs only after the repro is small.

If you want a second draft of a patch, MonkeyCode’s free model access and free server option can host that loop. Keep the harness anyway. The tail can still outrun the bytes.