Why a ring buffer's capacity must divide 2^64

2026-11-08 · 10 min read

The simplest single-producer single-consumer ring keeps two counters that are never reset and masks them on every access. That shape turns the full and empty tests into one subtraction and takes the modulo off the hot path, but it also pulls the counters' own 64-bit overflow into the correctness of the queue: when an index wraps, the slot it addresses after the wrap has to continue the sequence from before it. That holds only when the capacity divides 2^64. So a power-of-two capacity is a correctness condition rather than a performance preference, and the difference shows up exactly once in the life of a process.

I keep a small header-only version of this queue with the reasoning written down next to the code, spscring. The README opens by listing the three ways these queues are usually wrong, and the third one is this: a counter that wraps at a non-multiple of the capacity, so the queue silently reorders once, years in. This post is that item in full.

The shape that makes the overflow matter#

The indices only grow. No branch sends them back to zero, no wrapped flag, no modulo anywhere on the hot path.

// Indices count forever and are masked at use. Subtraction is correct
// across the unsigned wrap, and because the capacity is a power of two the
// wrap does not shift the alignment.
alignas(cache_line) std::atomic<std::size_t> write_{0};
alignas(cache_line) std::atomic<std::size_t> read_{0};

A push addresses slots_[write & (Capacity - 1)] and a pop addresses slots_[read & (Capacity - 1)]. Fullness is write - read == Capacity. A pop proceeds while read != write. The teardown path walks the same way:

void destroy_queued() noexcept {
    const std::size_t read = read_.load(std::memory_order_relaxed);
    const std::size_t write = write_.load(std::memory_order_relaxed);
    for (std::size_t index = read; index != write; ++index) element(index)->~T();
}

Every one of those expressions is unsigned arithmetic modulo 2^64, and every one of them stays correct when the counter rolls over: the subtraction because the true difference never exceeds the capacity, so the mod-2^64 result is the true difference, and the loop because it compares for inequality rather than ordering. size() is the one place where a third thread can be fooled, and it is handled by load order and a clamp instead of by pretending the wrap does not happen:

[[nodiscard]] std::size_t size() const noexcept {
    const std::size_t read = read_.load(std::memory_order_acquire);
    const std::size_t write = write_.load(std::memory_order_acquire);
    return std::min(write - read, ring_capacity());
}

So the arithmetic survives. What does not survive on its own is the mapping from index to slot.

What a capacity of 1000 actually does#

Say the counters are the same but the capacity is a round number and the slot comes out of a modulo. This is the shape I am not shipping:

// The common wrong version: a capacity that does not divide 2^64.
static constexpr std::size_t capacity = 1000;
T* slot(std::size_t index) { return &slots_[index % capacity]; }

The hardware has already folded the counter before your % runs, so the slot for the n-th operation is (n mod 2^64) mod 1000, not n mod 1000. Those two functions agree until the fold does something, and then they diverge, because 1000 does not divide 2^64. The leftover is concrete: 2^64 is 18446744073709551616, so 2^64 mod 1000 is 616.

Follow one slot through that. Before the rollover, slot 0 was last written by index 2^64 - 616, since that index is the largest multiple of 1000 below 2^64. After the rollover, index 0 also wants slot 0. The two indices are 616 apart, and the queue's own rule allows up to 1000 indices to be live at once. If the queue is holding 616 or more elements at the instant the write index crosses zero, the producer builds a new element on top of one the consumer has not taken yet. The consumer then pops that position and gets the wrong element, pops forward, and finds the newer element still sitting there. One lap later the aliasing is gone and the queue is correct again, for the next 2^64 operations.

Two things make this the worst failure class I know of in this kind of code.

It is depth-dependent. Both threads compute the slot the same way from the same index, so they never disagree with each other; what breaks is the invariant that the live window of indices occupies distinct slots. Whether anything is lost depends on how deep the queue happens to be at one particular instant. A queue that is usually near-empty crosses the rollover untouched and you never learn that it was a coin flip.

It is also out of reach of brute force. The counter is 64 bits. At one operation per nanosecond, 2^64 operations take about 584 years; at a hundred million operations per second, about 5.8 years of continuous traffic. The demo in that repository pushes a million messages through a ring<message, 4096> and the threaded test moves two hundred thousand std::uint32_t through a heap_ring of 1024 slots. Neither of those gets within an astronomical distance of the condition. Throughput tests cannot find this, a fuzzer cannot find this, and a code review that reads % capacity as an innocuous spelling of & (capacity - 1) will not find it either. I have spent most of the last several years on payment and crypto systems, where a fault that fires once and then clears itself is the expensive kind: somebody has to explain a single mismatched record, and the code that produced it looks fine when they go read it.

The fix is not to detect the rollover. It is to pick a capacity that divides the counter's modulus. For a 64-bit counter that means a power of two, and once the capacity is a power of two, the modulo is an AND and the hot path gets faster for free. The correctness decision and the performance decision are the same decision, which is why I think the performance framing is dangerous: it makes the requirement sound negotiable.

A condition the compiler checks#

If it is a correctness condition, it should not be a sentence in a README. For the fixed-capacity ring it is a static_assert:

static_assert(detail::is_power_of_two(Capacity), "capacity must be a power of two");

with the predicate written the plain way:

constexpr bool is_power_of_two(std::size_t n) noexcept {
    return n != 0 && (n & (n - 1)) == 0;
}

ring<int, 1000> is a compile error instead of a queue that works until the counter wraps.

A capacity that is only known at start-up cannot be checked that way, so the heap variant moves the check into a factory that is allowed to fail. heap_ring<T>::create(n) returns a null pointer rather than a queue it cannot honour, and the test pins down what it refuses:

void create_refuses_a_capacity_it_cannot_honour() {
    CHECK(spscring::heap_ring<int>::create(0) == nullptr);
    CHECK(spscring::heap_ring<int>::create(3) == nullptr);
    CHECK(spscring::heap_ring<int>::create(1000) == nullptr);  // not quietly 1024
    // 2^63 slots of two bytes each is 2^64 bytes, which is not a size_t.
    CHECK(spscring::heap_ring<std::uint16_t>::create(std::size_t{1} << 63) == nullptr);
}

The comment on the third line is the part I care about. Rounding 1000 up to 1024 is the friendly-looking choice and it is wrong twice over: it silently changes the caller's memory footprint, and it hides the fact that the number in their configuration file was never a capacity this queue could have. The honest answers are the capacity that was asked for, or none, and the caller gets to decide what to do about it.

Exercising a wrap you cannot reach#

An invariant that no test touches is a comment. To test the rollover you have to put the indices near it, which means reaching inside the queue, and the usual ways of doing that all leave something behind in the shipped library. Public indices invite a caller to write them. An #ifdef means the thing you tested was not the thing you shipped. A named friend class drags the test's identity into the header.

What the header does instead is declare a template and define it nowhere:

namespace detail {
template <typename Ring> struct test_access;  // declared here, defined nowhere
}

ring names detail::test_access<ring> as a friend. A translation unit that supplies the definition gets at the indices; a build that does not define it has no way to reach them, because there is nothing to instantiate. The whole hook costs the library one declaration and one friend line, with no macro and no build variant. The definition lives in the test file:

namespace spscring::detail {

template <typename Ring>
struct test_access {
    // Called before any thread touches the ring, so relaxed stores are enough.
    static void start_indices_at(Ring& queue, std::size_t index) {
        queue.write_.store(index, std::memory_order_relaxed);
        queue.read_.store(index, std::memory_order_relaxed);
    }
};

}  // namespace spscring::detail

With that, the wrap becomes a short test. It starts both indices six short of the end, runs 32 elements through bursts of four, three, two and one, and checks every value out, the refusal of a fifth push into a full queue on both sides of the rollover, and the count in the state where the write index has passed zero and the read index has not:

using small_ring = spscring::ring<int, 4>;
constexpr std::size_t start = SIZE_MAX - 5;

small_ring q;
spscring::detail::test_access<small_ring>::start_indices_at(q, start);
CHECK(q.empty());

The burst sizes are there so the queue sits at four different depths when the counter crosses zero, and that depth is the variable that decides whether a broken capacity loses anything. The test ends by asserting that the run actually reached the rollover with the queue non-empty where it mattered, because a wrap test that never reaches the wrap passes cheerfully and proves nothing. That is a failure mode of the test rather than of the queue, and no less real for it.

What I would do differently#

I would write the wrap test before the threaded one. The two-thread test that pushes two hundred thousand elements through a 1024-slot ring is the test that feels like proof, it is the one that catches a missing release store on hardware that does not forgive it, and it exercises the index arithmetic only in the region where the arithmetic is boring. Writing it first gave me a green suite that said nothing about the one bug in this class that survives a green suite.

I would also be slower to add the run-time capacity. The fixed-capacity ring has this problem solved by the compiler, with a message a caller can read. Every refusal create has to make, zero, a non-power-of-two, a byte size that overflows size_t, exists because a number arrived too late for the static_assert. That is a reasonable price when the capacity genuinely comes from configuration, and pure cost when it does not.

The general lesson is narrower than it looks. It is not that unsigned overflow is subtle; the subtraction here is correct across the wrap and the comments say why. It is that when you remove a reset, the counter's modulus becomes a parameter of your data structure, and you now owe an argument that your capacity and that modulus agree. For a 64-bit index there is exactly one family of capacities that satisfies it, and the compiler is perfectly capable of insisting on it.