This project implements a concurrent lock-free queue in Rust. The goal is to study to what extent Rust's type system and tools such as Miri and Loom guarantee (or fail to guarantee) safety when implementing this algorithm.
The implementation is based on the Scalable Circular Queue (SCQ)1, which builds a lock-free ring buffer through indirection. A reason to use bounded memory is that "typical system memory allocators are not lock-free. Lock-based allocators can defeat the purpose of creating a purely lock-free algorithm"1. Indirection serves the same goal: data entries cannot generally be updated by a single atomic instruction, whereas fixed-width indices can.
The main finding is that the hard part, the two index queues, is implemented entirely in safe Rust. unsafe appears only in the data array and in the Send/Sync implementations, whose correctness the type system cannot check and which are validated with Miri and Loom instead.
The entry here refers to the element stored in the two index queues. Each entry has 3 fields, the index, the cycle, and a Boolean indicating whether it is safe for an enqueuer to use this entry. The algorithm requires the entry to support atomic instructions. So, the 3 fields are packed into PackedEntry, and a few atomic primitives are implemented in AtomicEntry, whose underlying raw field is an AtomicU64, which is the widest atomic type that Rust's standard library supports. Because of the way the entry is packed, a tricky problem emerges: the is_safe needs one bit, and if index takes up 32 bits, then there are only 31 bits left for cycle. Normally this is fine but in this algorithm, when comparing the entry's cycle and the cycle of the index to be enqueued, a wrapping_sub is needed to correctly identify which cycle is older. The solution is to compare the "sign bit" at bit 30 of the wrapping_sub's result.
Sciq is the index queue that stores AtomicEntry. It implements the following functions in safe Rust:
Scq<T> is where the data entries are managed based on the two Sciqs, aq and fq, which stand for acquired index queue and freed index queue respectively. All unsafe code is confined here: writing and reading the data slots via UnsafeCell<MaybeUninit<T>>, and the Send/Sync implementations.
Box<[T]> is an owned boxed slice used in Scq as Box<[UnsafeCell<MaybeUninit<T>>]> to store the data buffer and used in the index queues to hold their entries in a Box<[AtomicEntry]>. This type provides two safety guarantees: First, ownership guarantees that the heap allocation is freed exactly once when the Scq / Sciq is dropped, eliminating the possibility of double-free, use-after-free or leaks with no manual free. Second, the slice is a fat pointer with its length, so every access is checked at runtime and an out-of-range index panics instead of reading or writing arbitrary memory. So, there is no chance of buffer overflow bugs that an equivalent C array would expose.
All the atomic primitives used in this project are safe functions guaranteed by the standard library (or loom). The type system therefore guarantees freedom from data races and undefined behavior regardless of the ordering chosen. But an incorrect memory ordering can still produce incorrect results.
The implementation uses u32 indices, u64 head / tail counters, and usize slice offsets. Rust has strict numeric conversion rules that refuse to convert between these types implicitly. In C, there are implicit integer promotion and truncation, whereas in Rust, every width or sign change must be written explicitly. Again, Rust helps prevent unintentional numeric conversions, but it cannot prevent logic errors due to wrong explicit conversions.
As a concurrent queue, Scq must mutate data through a shared reference, because in Rust, a mutable reference is exclusive, the data entries are stored in a Box<[UnsafeCell<MaybeUninit<T>>]>. UnsafeCell<T> allows obtaining a *mut T from a shared reference and mutating through it. The downside is that UnsafeCell<T> does not check whether the mutation is actually safe, that is, that no two threads mutate the same slot concurrently. This must instead be guaranteed by the correctness of the algorithm and a correct implementation.
After construction, the bounded queue should have allocated the memory it uses and should never allocate any memory again, but semantically the queue is empty, so either T should be required to implement Default to fill the data array, or the data array should skip initialization. MaybeUninit<T> represents memory that is the right size and alignment for a T but may not yet hold one. When reading such memory, an unsafe block is required and it is the coder's obligation to ensure the memory has been initialized before assume_init_read().
A side effect of MaybeUninit<T> is that when the queue goes out of scope, Rust will not drop the T values inside, because it cannot tell which slots are initialized. Scq therefore implements Drop manually, dequeuing every remaining element so that each initialized value is dropped.
To be shared across threads, Scq<T> must be Send and Sync. But because it contains UnsafeCell, these two traits have to be implemented explicitly.
Before testing any concurrency, Scq should be a correct data structure when running on a single thread. Its behavior is compared against std::collections::VecDeque as a reference. The test does thousands of randomly chosen enqueue/dequeue operations to both structures for a randomly sized capacity.
The mpmc test spawns 300 producers and 300 consumers sharing one Scq through an Arc, with each producer enqueuing 10,000 distinct integers and each consumer dequeuing the same number. Because every produced value is unique, all the values the consumers get can be gathered to check for any duplications or losses, but this test does not check the FIFO correctness.
The mp1c test keeps 300 producers but a single consumer, and additionally records the dequeue order of each value; it then asserts that, for every individual producer, its values are consumed in the order they are produced, verifying the FIFO property.
Loom exhaustively explores all the possible thread interleavings of a small program. However, loom can only see concurrency that runs through its own primitives, so the implementation has to be compiled under #[cfg(loom)]. The tail, head and threshold counters that control the retry loops of the algorithm could not be tested under loom, because the permutations would explode even in a small-scale test.
Miri is an interpreter for Rust's mid-level IR (MIR) that aims to detect undefined behavior in the unsafe code. The two Miri tests are just shrunk-down copies of the multi-threaded tests. The reason is that Miri is slow, because it interprets MIR in a virtual machine and has to keep track of much information to find possible undefined behavior.
All the tests in the project passed. The single- and multi-threaded tests confirm the FIFO and capacity semantics with no lost or duplicated elements. The Loom tests report no ordering violation across the interleavings they explore, and Miri finds no undefined behavior on the runs it interprets. Together they give strong evidence that the implementation is correct.
- The Loom verification is incomplete: the
head,tail, andthresholdcounters are not brought to loom tests. - The SCQ algorithm is relatively easy to implement compared with its unbounded version and WCQ, the wait-free concurrent queue.2 This case study could be extended by implementing these algorithms to better verify the boundary of Rust's safety guarantees.
- Miri seems interesting and might be worth the effort to study on its own.
Footnotes
-
R. Nikolaev, “A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue,” LIPIcs, Volume 146, DISC 2019, vol. 146, p. 28:1-28:16, 2019, doi: 10.4230/LIPIcs.DISC.2019.28. ↩ ↩2
-
R. Nikolaev and B. Ravindran, “wCQ: A Fast Wait-Free Queue with Bounded Memory Usage,” arXiv.org. Accessed: Jun. 05, 2026. [Online]. Available: https://arxiv.org/abs/2201.02179v2 ↩