A single-producer single-consumer ring buffer

Build a single-producer, single-consumer (SPSC) ring buffer from atomics and pass every item through it from one thread to another.

pub fn spsc_roundtrip(items: Vec<i64>, capacity: usize) -> Vec<i64>

A ring buffer is a fixed array of slots used as a queue: writers fill slots in order, readers empty them in the same order, and both wrap around to slot 0 after the last slot. "Single producer, single consumer" means exactly one thread adds items and exactly one thread removes them.

The contract

• Create a buffer with capacity slots. A capacity of 0 is treated as 1.
• Start one producer thread that pushes the items in input order, and one consumer thread that removes exactly items.len() values and collects them.
• Return the consumer's values. The result must equal items exactly: the same values in the same order. Values can be any i64, including negatives, zeros and duplicates.
• capacity can be much smaller than the number of items, so the producer must wait whenever the buffer is full and the consumer must wait whenever it is empty.
• Empty input returns an empty Vec. You may return it without starting any threads.
• Use no Mutex and no channel: two atomic indices and an array of atomic slots.

The tests use capacities from 1 to 100 and at most 201 items, so allocating capacity slots up front is fine. The tests compare only the returned vector. They cannot see whether you used two threads, a lock, or the right memory orderings, so those parts of the exercise are checked by your own reasoning, not by the grader.

Why one producer and one consumer keeps it small

With exactly one producer and one consumer, each index has exactly one writer. head counts the items written so far and is stored only by the producer. tail counts the items read so far and is stored only by the consumer. Each side keeps its own count in a local variable and only loads the other side's atomic.

So no compare-and-swap or other read-modify-write operation is needed. When a side cannot proceed, it waits in a loop until the other side's index changes.

The protocol

Let both counters only ever increase, and find the slot for item number k with k % capacity. Then full and empty are easy to tell apart:

empty  when  head == tail
full   when  head - tail == capacity

The consumer never gets ahead of the producer, so tail <= head always holds and head - tail cannot underflow. In this exercise the counters never exceed items.len(), so they cannot overflow either. A queue that runs forever would need wrapping arithmetic, and usually a power-of-two capacity so that % capacity stays consistent when a counter wraps.

The other common design keeps both indices in 0..capacity. Then head == tail could mean either full or empty, which is why such buffers often leave one slot unused or keep a separate item count.

In outline (these are fragments, not a complete program; Acquire, Release and Relaxed stand for the std::sync::atomic::Ordering variants, and h and t are each thread's local copy of its own index):

Producer, for each item:

while h - tail.load(Acquire) == cap { spin_loop(); }   // wait while full
buf[h % cap].store(item, Relaxed);                     // fill the slot
h += 1;
head.store(h, Release);                                // publish the item

Consumer, for each item:

while head.load(Acquire) == t { spin_loop(); }         // wait while empty
let v = buf[t % cap].load(Relaxed);                    // read the slot
t += 1;
tail.store(t, Release);                                // hand the slot back

Why each ordering is what it is

A Release store and an Acquire load that reads the stored value form a pair: everything the storing thread did before the store happens before everything the loading thread does after the load.

• head. The producer writes the slot, then stores head with Release. When the consumer's Acquire load of head sees the new value, the slot write is guaranteed to be visible, so the consumer reads the item and not an older value.
• The slots. The slot accesses can be Relaxed because they do not do the synchronizing. They are the data being handed over, and the index operations around them provide the ordering.
• tail. This is the same pairing in the other direction. The consumer reads the slot, then stores tail with Release. When the producer's Acquire load of tail sees that value, the consumer's read is guaranteed to have happened before the producer overwrites the slot.

Passing tests do not prove these orderings are right. If one of them were weakened to Relaxed, the program would be wrong, but because every slot is an atomic it would not be undefined behavior: the consumer could read a slot before the item arrives or after it has been overwritten. That can stay invisible in testing. On x86-64, ordinary loads and stores already have acquire and release ordering in hardware, and on other processors such reorderings depend on timing. The compiler may also reorder Relaxed operations, so the weakened version is not correct on any platform. The argument above, not a passing run, is what shows the orderings are enough.

The starter's error

error[E0499]: cannot borrow `buf` as mutable more than once at a time

The starter uses a plain Vec<i64> and creates two mutable references to it, one for the producer and one for the consumer. Rust allows only one &mut borrow of a value to be active at a time. The two threads never actually touch the same slot at the same moment, but that is guaranteed by the index protocol at run time, and the borrow checker does not analyze it. The diagram shows the same error in miniature: b borrows v mutably while a is still in use.

Since the indices are already atomics, make the slots atomics too: Vec<AtomicI64>. An atomic can be changed through a shared reference (store takes &self), and AtomicI64 is Sync, so both threads can hold a plain & to the same Vec<AtomicI64> and no unsafe code is needed. (AtomicI64 exists only on targets that support 64-bit atomic operations, which includes the common 64-bit platforms.)

A ring buffer for any element type T usually stores UnsafeCell<MaybeUninit<T>> slots and uses unsafe code, and its author must prove that the protocol keeps the two threads off the same slot. Using i64 lets you learn the protocol without that proof.

About the waiting loops

std::hint::spin_loop() tells the processor that the thread is busy-waiting. The standard library documents that the processor may use this to save power or switch hyper-threads, and that on some platforms it does nothing. On 64-bit ARM, Rust 1.98.1 compiles it to the isb instruction. It does not affect correctness, but it belongs in every wait loop.

Clippy has a lint for a missing hint, clippy::missing_spin_loop, which warns about a while loop with an empty body whose condition loads an atomic. In checks with Clippy 1.98.1, it fired when the atomic was a local variable but not when it was reached through a reference or an Arc, which is how the threads in this problem reach it. So Clippy will probably not remind you here; add the hint yourself.

A spinning thread keeps a CPU core busy for the whole wait, so spinning suits waits that are expected to be short. Here each wait ends as soon as the other thread takes one step. When the other side may be idle for a long time, a common approach is to spin a bounded number of times and then block, for example with thread::park and Thread::unpark.