The Empty Check Passed on a Full Ring

The ring reported empty after a full lap. Full and empty shared one modulus check. I lost every payload and still kept green tests.

Why did review miss this quiet bug? The happy path never filled the whole buffer.

The Symptom

I filled a four-slot ring inside a unit test. I pushed four times and never popped once. Then empty() returned true and dropped the batch.

There was no crash and no sanitizer line. CI never failed an assert on this path.

The alias is defined behavior, so UBSan stayed quiet. The only signal was a missing payload later.

Does that failure sound like a data race? It was not a race in this file.

I had one thread and one tight loop. I also had one copied empty predicate.

Build the Smallest Liar

Follow this sequence without skipping a dump. Do not start with a million slot ring.

1. Build a ring whose capacity is a tiny power of two.
2. Push exactly cap items with no intervening pops.
3. Call empty() before you pop a single item.
4. Watch empty() return true while live bytes remain.

I keep the liar in a file named ring_empty_lie.cpp. The core of the liar sits below this paragraph.

#include <cstddef>
#include <iostream>
#include <vector>

struct Ring {
    std::vector<int> buf;
    std::size_t cap;
    std::size_t r = 0;
    std::size_t w = 0;

    explicit Ring(std::size_t n) : buf(n, 0), cap(n) {}

    // Bug: modulus equality cannot tell full from empty.
    bool empty() const { return (w % cap) == (r % cap); }

    void push(int v) {
        buf[w % cap] = v;
        ++w;
    }

    bool pop(int& out) {
        if (empty()) return false;
        out = buf[r % cap];
        ++r;
        return true;
    }
};

int main() {
    Ring ring(4);
    for (int i = 1; i <= 4; ++i) ring.push(i);
    std::cout << std::boolalpha
              << "empty=" << ring.empty()
              << " w=" << ring.w
              << " r=" << ring.r << "\n";
    int x = 0;
    int n = 0;
    while (ring.pop(x)) ++n;
    std::cout << "popped=" << n << "\n";
    return n == 0 ? 1 : 0;
}

Compile the file with sanitizers and low optimization.

g++ -std=c++17 -O1 -g -Wall -Wextra -fsanitize=address,undefined \
    -o ring_empty_lie ring_empty_lie.cpp
./ring_empty_lie
echo $?

You should see empty=true and popped=0 on stdout. The process exits with status one here. That print shows the entire protocol bug.

Walk the Cursors

Dump cursor state at the failing assert. Do not guess those residues from memory.

1. Print raw w and r before any modulus.
2. Print w % cap and r % cap after that.
3. Print how many pushes you actually issued.
4. Compare occupied w - r against the cap.

After four pushes, w is four and r is zero. w % 4 is zero and r % 4 is zero.

The predicate says empty with four live slots. Occupied is four, so the check disagrees.

Who holds the truth in this dump? The occupied count holds the real truth. The modulus check is the real liar.

On larger rings the same lie waits. It only needs one exact capacity fill. Most of my tests stopped one below capacity.

Root Cause

I wanted one cheap empty check in the hot path. I copied the textbook head equals tail rule. I then stored unbounded cursors and reduced them with modulus only inside the check.

The head equals tail rule needs a gap. It fails when full wraps to the same residues.

I left no unused gap slot in the ring. I also skipped a separate occupancy count. Full and empty became the same picture.

Was this undefined behavior under the standard? No, it was only a wrong invariant.

Sanitizers do not know your ring protocol. They only know invalid memory use here. This bug never left the ring object.

Wrong Fixes I Almost Shipped

I almost added a boolean is_empty flag. That flag drifts as soon as two writers exist.

I almost used w minus r with 32-bit cursors. That form wraps too, just much later.

I almost kept modulus and reserved one slot. That design works if full is tested.

I still needed a test that fills to the new full. Without that test I would ship the next lie.

Debugging Sequence I Now Reuse

I run these steps on every silent drop. I refuse to start this hunt with threads.

1. Shrink capacity to four or eight slots.
2. Drive exact fills for cap-1, cap, and cap+1.
3. Record cursors on every push and every pop.
4. Assert w minus r against the visible occupancy.
5. Add threads only after the single-thread oracle is mean.

Why start with this brutal step order? Tiny rings lap inside a single test.

Huge rings hide the residue collision for days. Threads on a lying empty() only add noise.

Artifact: Oracle Asserts and a Decision Table

These are proposed tests, not a production incident dump.

#include <cassert>
#include <cstddef>
#include <vector>

struct Ring {
    std::vector<int> buf;
    std::size_t cap;
    std::size_t r = 0;
    std::size_t w = 0;

    explicit Ring(std::size_t n) : buf(n, 0), cap(n) {}

    std::size_t occupied() const { return w - r; }
    bool full() const { return occupied() == cap; }
    bool empty() const { return occupied() == 0; }

    bool push(int v) {
        if (full()) return false;
        buf[w % cap] = v;
        ++w;
        return true;
    }

    bool pop(int& out) {
        if (empty()) return false;
        out = buf[r % cap];
        ++r;
        return true;
    }
};

int main() {
    Ring ring(4);
    int x = 0;
    assert(ring.empty());
    assert(ring.push(1) && ring.push(2) && ring.push(3));
    assert(!ring.full());
    assert(ring.push(4));
    assert(ring.full());
    assert(!ring.empty());  // the old check failed here
    assert(ring.occupied() == 4);
    assert(!ring.push(5));  // must reject
    assert(ring.pop(x) && x == 1);
    assert(ring.push(5));
    assert(ring.occupied() == 4);
    return 0;
}

I pin this decision table next to the test.

Keep the table beside the failing binary. It beats rereading the same cursor dump.

Commands I Actually Type

I want a failing binary before any theory. Then I want a log of both cursors.

g++ -std=c++17 -O1 -g -fsanitize=address,undefined -o ring_fix ring_fix.cpp
./ring_fix

g++ -std=c++17 -O1 -g -fsanitize=thread -o ring_tsan ring_fix.cpp
# only after the single-thread oracle is in place

GDB helps when the assert fires too late.

gdb -q ./ring_empty_lie
(gdb) break Ring::empty
(gdb) run
(gdb) print w
(gdb) print r
(gdb) print cap
(gdb) print (w % cap) == (r % cap)

Ask the debugger the same occupancy question. Do not ask your memory for residues.

Where a Scratch Model Fits

I still write the occupancy oracle by hand. I only want extra negative cases after that.

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

I draft fill-boundary tests with MonkeyCode free model access. I compile throwaway variants on the free server option.

I paste every candidate into the local sanitizer build. The model does not get to decide green.

Ask it for cap-1, cap, and cap+1 cases. Ask it for a wrap after a single pop.

Do not ask it to certify the ring. You own the occupancy assert in review.

Need a spare box for those extra cases? The free server option is one path. Keep the verdict on your own machine.

Limitations

This workflow does not catch a true data race. TSan comes after the sequential oracle exists.

Occupancy w minus r assumes r never outruns w. Thirty-two bit cursors still wrap under long soaks. Use sixty-four bit positions unless lifetime is proven.

Generated tests are only the cases you named. They omit the case you did not describe.

A free model will repeat head equals tail from blogs. That is how I got the first lying check.

The free server is not your release builder. Do not put secrets on a shared scratch box. Do not treat a remote compile as a sanitizer run.

Who Should Not Use This Approach

Skip it if you cannot shrink the ring. Skip it if you ship without a local ASan build.

Skip it if you need a proved wait-free queue. Skip it if packed cursors need a different model.

Do not use generated tests as the only gate. Do not skip the occupancy oracle after a clean model reply.

What I Keep

I keep three fills in every ring test. I keep occupied() next to empty() in the header.

I keep capacity tiny until the protocol is mean. I keep sanitizers on the laptop that signs off.

The modulus check was cheap in the hot path. It was also a liar under an exact fill. Cheap predicates still need an occupancy oracle.