Implementation Walkthrough

Why this matters: this implementation is under forty lines, which means an interviewer will read every one of them. The grading question is whether each memory-ordering annotation is load-bearing in a way you can explain — a fence you can't justify is as damaging as one you forgot.

The structure

#define CAPACITY 1024                 // power of two, fixed at construction
#define MASK     (CAPACITY - 1)

struct record { char bytes[64]; };    // fixed-size POD, copied by value

struct ring {
    struct record slots[CAPACITY];

    atomic_u64 tail;   // written by producer only  (free-running)
    atomic_u64 head;   // written by consumer only  (free-running)
};

Say the ownership out loud as you write the two fields — "tail is the producer's, head is the consumer's, and nothing ever has two writers." That single sentence is your correctness argument's foundation, and interviewers listen for it.

try_push: the producer side

bool try_push(struct ring *r, const struct record *in) {
    u64 tail = atomic_load_relaxed(&r->tail);      // my own counter: no
                                                   // ordering needed to
                                                   // read my own writes
    u64 head = atomic_load_acquire(&r->head);      // consumer's counter

    if (tail - head == CAPACITY)                   // full: reject, don't block
        return false;

    r->slots[tail & MASK] = *in;                   // 1. write the record

    atomic_store_release(&r->tail, tail + 1);      // 2. THEN publish it
    return true;
}

Three narration points, in the order an interviewer will probe them:

The full check. tail - head == CAPACITY is exact because both counters are free-running (lesson 02). If the check passes stale — the consumer has since consumed more — the buffer merely looks fuller than it is and we reject a push that could have succeeded. That's a conservative error: annoying, never incorrect. Say this; it shows you asked "what if this value is stale?" about every load, which is the systems-interview reflex being graded.

The acquire on head. This is slot-reuse protection (invariant 5): observing the consumer's counter with acquire guarantees the consumer's reads of the slot we're about to overwrite happened-before our write. Without it, we could scribble over bytes the consumer is still copying out.

The release on tail. The publish rule (invariant 4): the record bytes at step 1 are guaranteed visible to anyone who acquire-loads the new tail. Write, then publish — the order of those two lines is the whole correctness story, and swapping them is the bug this problem exists to catch.

try_pop: the consumer side, mirrored

bool try_pop(struct ring *r, struct record *out) {
    u64 head = atomic_load_relaxed(&r->head);      // my own counter
    u64 tail = atomic_load_acquire(&r->tail);      // producer's counter:
                                                   // makes the record
                                                   // bytes visible too
    if (tail - head == 0)                          // empty
        return false;

    *out = r->slots[head & MASK];                  // 1. read the record

    atomic_store_release(&r->head, head + 1);      // 2. THEN free the slot
    return true;
}

The symmetry is exact, and pointing it out is efficient narration: each side relaxed-loads its own counter, acquire-loads the other's, does its data movement, then release-stores its own counter. The consumer's release on head is what the producer's acquire pairs with — it says "my read of this slot is complete; overwriting it is now safe."

A staleness note worth volunteering here too: if the consumer's acquire-load of tail is a moment behind, the buffer merely looks emptier than it is — again conservative, again never incorrect. Both indices err only in the safe direction; that asymmetry is a property of the design, not luck.

The one-line wrap

tail & MASK is the entire circularity of the "circular" buffer. It costs one AND because we required power-of-two capacity in the requirements act — the moment where that early question pays off, and worth a five-second callback when you write this line: "this is why I asked for a power of two."

What you'd say about complexity

Both operations are O(1) and allocation-free: two atomic loads, one 64-byte copy, one atomic store. No syscalls, no locks, no branches beyond full/empty. The honest cost model an interviewer wants to hear: the copy dominates, the atomics are cheap when uncontended — and the design's remaining performance story is about cache lines, which is exactly where the next lesson picks up.

Key takeaway

try_push and try_pop are perfect mirrors: relaxed-load your own counter, acquire-load the other side's, move the bytes, release-store your own counter. The two release/acquire pairs enforce the two data invariants — records are visible before the tail says so, slots are reusable only after the head says so — and every stale read errs conservatively. Under forty lines, every annotation defensible: that's the bar.