Skip to main content

nure_queue/
lib.rs

1//! `nure-queue`: a `no_std`, allocator-free, lock-free bounded MPMC queue.
2//!
3//! A port of Crossbeam's [`ArrayQueue`](https://docs.rs/crossbeam-queue) (Dmitry
4//! Vyukov's bounded MPMC algorithm) to static storage: no heap, no allocator,
5//! constructible in `const` context so it can live in a `static`.
6//!
7//! ```rust
8//! use nure_queue::Queue;
9//!
10//! let q = Queue::<u32, 8>::new();
11//! q.enqueue(1).unwrap();
12//! q.enqueue(2).unwrap();
13//! assert_eq!(q.dequeue(), Some(1));
14//! assert_eq!(q.dequeue(), Some(2));
15//! ```
16//!
17//! Static, allocator-free construction (default build only,
18//! demonstrated by `static_construction_no_alloc` in `tests/smoke.rs`):
19//! ```ignore
20//! use nure_queue::Queue;
21//!
22//! static Q: Queue<u32, 8> = Queue::new();
23//! ```
24//!
25//! # Why this exists
26//!
27//! `heapless::mpmc` is deprecated (not truly lock-free — see
28//! [heapless#583](https://github.com/rust-embedded/heapless/issues/583)).
29//! Crossbeam's `ArrayQueue` is correct but heap-allocates on construction.
30//! `embassy-sync`'s channel is static but mutex-based. This crate is the
31//! intersection: static + truly lock-free.
32//!
33//! # Memory ordering
34//!
35//! Same protocol as Crossbeam: slot hand-off via acquire/release stamps,
36//! head/tail CAS with `SeqCst` on success. See `push`/`pop` for details.
37
38#![cfg_attr(not(any(test, feature = "std")), no_std)]
39#![warn(missing_docs)]
40
41use core::{fmt, mem::MaybeUninit};
42
43// ---------------------------------------------------------------------------
44// Atomics shim: core by default, loom via the `loom` cargo feature
45// ---------------------------------------------------------------------------
46#[cfg(feature = "loom")]
47mod atom {
48    pub use loom::cell::UnsafeCell;
49    pub use loom::sync::atomic::{AtomicUsize, Ordering, fence};
50    pub type AtomicIndex = AtomicUsize;
51    pub type Index = usize;
52}
53
54#[cfg(not(feature = "loom"))]
55mod atom {
56    #![allow(unused_imports)]
57    pub use core::cell::UnsafeCell;
58    #[cfg(target_has_atomic = "64")]
59    pub use core::sync::atomic::AtomicU64;
60    pub use core::sync::atomic::{AtomicUsize, Ordering, fence};
61    #[cfg(target_has_atomic = "64")]
62    pub type AtomicIndex = AtomicU64;
63    #[cfg(target_has_atomic = "64")]
64    pub type Index = u64;
65    #[cfg(not(target_has_atomic = "64"))]
66    pub type AtomicIndex = AtomicUsize;
67    #[cfg(not(target_has_atomic = "64"))]
68    pub type Index = usize;
69}
70
71#[allow(unused_imports)]
72use atom::*;
73
74// ---------------------------------------------------------------------------
75// Helpers
76// ---------------------------------------------------------------------------
77
78/// Cache-line padded wrapper so `head` and `tail` don't share a line.
79#[repr(align(64))]
80struct Padded<T>(T);
81
82/// Backoff: exponential spinning; with `std` it yields past a threshold
83/// (pure spin on `no_std`, where yielding does not exist).
84struct Backoff {
85    spins: u32,
86}
87
88impl Backoff {
89    #[inline]
90    fn new() -> Self {
91        Self { spins: 0 }
92    }
93
94    #[inline]
95    fn spin(&mut self) {
96        #[cfg(feature = "std")]
97        if self.spins > 6 {
98            std::thread::yield_now();
99            return;
100        }
101        let n = 1u32 << self.spins.min(6);
102        for _ in 0..n {
103            core::hint::spin_loop();
104        }
105        if self.spins < 8 {
106            self.spins += 1;
107        }
108    }
109
110    #[inline]
111    fn snooze(&mut self) {
112        #[cfg(feature = "std")]
113        if self.spins > 8 {
114            std::thread::yield_now();
115            return;
116        }
117        let n = 1u32 << self.spins.min(8);
118        for _ in 0..n {
119            core::hint::spin_loop();
120        }
121        if self.spins < 10 {
122            self.spins += 1;
123        }
124    }
125}
126
127/// Smallest power of two strictly greater than `cap` (`cap >= 1`, no overflow
128/// for realistic capacities; construction asserts a sane bound).
129const fn one_lap_for(cap: Index) -> Index {
130    let need = cap + 1;
131    let mut lap: Index = 2;
132    while lap < need {
133        lap *= 2;
134    }
135    lap
136}
137
138// ---------------------------------------------------------------------------
139// Slot
140// ---------------------------------------------------------------------------
141
142/// One queue slot: a stamp for the Vyukov protocol + uninitialized payload.
143struct Slot<T> {
144    // Loom atomics must NOT sit inside UnsafeCell (double tracking).
145    #[cfg(not(feature = "loom"))]
146    stamp: UnsafeCell<AtomicIndex>,
147    #[cfg(feature = "loom")]
148    stamp: AtomicIndex,
149    value: UnsafeCell<MaybeUninit<T>>,
150}
151
152impl<T> Slot<T> {
153    #[cfg(not(feature = "loom"))]
154    /// SAFETY: caller owns this slot per the Vyukov protocol (unique index
155    /// acquired via tail CAS), so exclusive access holds.
156    #[inline]
157    pub(crate) fn write_value(&self, value: T) {
158        unsafe { self.value.get().write(MaybeUninit::new(value)) }
159    }
160
161    #[cfg(not(feature = "loom"))]
162    #[inline]
163    pub(crate) fn read_value(&self) -> T {
164        unsafe { self.value.get().read().assume_init() }
165    }
166
167    #[cfg(not(feature = "loom"))]
168    #[inline]
169    pub(crate) fn drop_value(&mut self) {
170        unsafe { self.value.get_mut().assume_init_drop() }
171    }
172
173    #[cfg(not(feature = "loom"))]
174    /// Replaces the inner value, returning the old one.
175    /// SAFETY: caller owns this slot exclusively.
176    #[inline]
177    pub(crate) fn replace_value(&self, value: T) -> T {
178        unsafe {
179            let old = core::mem::replace(&mut *self.value.get(), MaybeUninit::new(value));
180            old.assume_init()
181        }
182    }
183
184    #[cfg(not(feature = "loom"))]
185    #[inline]
186    pub(crate) fn stamp_load(&self) -> Index {
187        unsafe { (*self.stamp.get()).load(Ordering::Acquire) }
188    }
189
190    #[cfg(not(feature = "loom"))]
191    #[inline]
192    pub(crate) fn stamp_store(&self, val: Index) {
193        unsafe { (*self.stamp.get()).store(val, Ordering::Release) }
194    }
195
196    #[cfg(feature = "loom")]
197    pub(crate) fn write_value(&self, value: T) {
198        // with_mut gives *mut MaybeUninit<T>; (&mut *p) is &mut MaybeUninit<T>.
199        // write returns &mut T; discard it.
200        self.value.with_mut(|p| unsafe {
201            let _ = (&mut *p).write(value);
202        })
203    }
204
205    #[cfg(feature = "loom")]
206    pub(crate) fn read_value(&self) -> T {
207        // with gives *const MaybeUninit<T>. ptr::read copies T out without moving.
208        self.value
209            .with(|p| unsafe { core::ptr::read(p).assume_init() })
210    }
211
212    #[cfg(feature = "loom")]
213    pub(crate) fn drop_value(&mut self) {
214        self.value
215            .with_mut(|p| unsafe { (&mut *p).assume_init_drop() })
216    }
217
218    #[cfg(feature = "loom")]
219    pub(crate) fn replace_value(&self, value: T) -> T {
220        self.value.with_mut(|p| unsafe {
221            core::ptr::replace(&mut *p, MaybeUninit::new(value)).assume_init()
222        })
223    }
224
225    #[cfg(feature = "loom")]
226    pub(crate) fn stamp_load(&self) -> Index {
227        self.stamp.load(Ordering::Acquire)
228    }
229
230    #[cfg(feature = "loom")]
231    pub(crate) fn stamp_store(&self, val: Index) {
232        self.stamp.store(val, Ordering::Release)
233    }
234}
235
236// ---------------------------------------------------------------------------
237// Queue
238// ---------------------------------------------------------------------------
239
240/// A bounded lock-free multi-producer multi-consumer queue with static storage.
241///
242/// Capacity `N` is fixed at compile time; the whole queue (including all
243/// slots) lives inline, so `Queue::new()` is `const` and the queue can be
244/// placed in a `static` with no allocator involved (requires the default
245/// build; with `loom` feature, use `Queue::new()` at runtime — see below).
246///
247/// `push` returns `Result<(), T>` on full push, `pop` returns `Option<T>` —
248/// plus [`Queue::enqueue`]/[`Queue::dequeue`] aliases matching the old
249/// `heapless::mpmc` API for drop-in migration.
250///
251/// # Static initialization
252///
253/// ```ignore
254/// // Default build: `Queue::new()` is `const`.
255/// static Q: Queue<u32, 8> = Queue::new();
256/// ```
257///
258/// With `--features loom`, `new()` is a regular function: construct at runtime.
259pub struct Queue<T, const N: usize> {
260    head: Padded<AtomicIndex>,
261    tail: Padded<AtomicIndex>,
262    // Array-of-MaybeUninit: `assume_init()` on `[Slot; N]` would transiently
263    // create uninitialized atomics (UB); each slot is written in `new()`.
264    buffer: [MaybeUninit<Slot<T>>; N],
265    one_lap: Index,
266}
267
268// SAFETY: synchronization via atomics; `T: Send` may cross threads.
269unsafe impl<T: Send, const N: usize> Sync for Queue<T, N> {}
270unsafe impl<T: Send, const N: usize> Send for Queue<T, N> {}
271
272impl<T, const N: usize> Default for Queue<T, N> {
273    fn default() -> Self {
274        Self::new()
275    }
276}
277
278impl<T, const N: usize> Queue<T, N> {
279    /// Creates an empty queue. `const`-compatible on the default build:
280    /// `static Q: Queue<u32, 8> = Queue::new();`.
281    ///
282    /// With the `loom` feature this is a regular (non-const) function
283    /// because loom's atomics are runtime-only; use it at runtime there.
284    #[cfg(not(feature = "loom"))]
285    pub const fn new() -> Self {
286        assert!(N > 0, "capacity must be non-zero");
287        assert!(N <= (isize::MAX as usize) / 2, "capacity is too large");
288
289        let mut buffer: [MaybeUninit<Slot<T>>; N] = unsafe { MaybeUninit::uninit().assume_init() };
290        let mut i = 0;
291        while i < N {
292            buffer[i] = MaybeUninit::new(Slot {
293                stamp: UnsafeCell::new(AtomicIndex::new(i as Index)),
294                value: UnsafeCell::new(MaybeUninit::uninit()),
295            });
296            i += 1;
297        }
298        Self {
299            head: Padded(AtomicIndex::new(0)),
300            tail: Padded(AtomicIndex::new(0)),
301            buffer,
302            one_lap: one_lap_for(N as Index),
303        }
304    }
305
306    /// Creates an empty queue (loom build: runtime-only, loom atomics
307    /// are not `const`-constructible).
308    #[cfg(feature = "loom")]
309    pub fn new() -> Self {
310        assert!(N > 0, "capacity must be non-zero");
311        assert!(N <= (isize::MAX as usize) / 2, "capacity is too large");
312
313        let mut buffer: [MaybeUninit<Slot<T>>; N] = unsafe { MaybeUninit::uninit().assume_init() };
314        let mut i = 0;
315        while i < N {
316            buffer[i] = MaybeUninit::new(Slot {
317                stamp: AtomicIndex::new(i as Index),
318                value: UnsafeCell::new(MaybeUninit::uninit()),
319            });
320            i += 1;
321        }
322        Self {
323            head: Padded(AtomicIndex::new(0)),
324            tail: Padded(AtomicIndex::new(0)),
325            buffer,
326            one_lap: one_lap_for(N as Index),
327        }
328    }
329
330    /// Capacity in elements. Always `N`.
331    #[inline]
332    pub const fn capacity(&self) -> usize {
333        N
334    }
335
336    fn push_or_else<F>(&self, mut value: T, f: F) -> Result<(), T>
337    where
338        F: Fn(T, Index, Index, &Slot<T>) -> Result<T, T>,
339    {
340        let mut backoff = Backoff::new();
341        let mut tail = self.tail.0.load(Ordering::Relaxed);
342
343        loop {
344            let index = (tail & (self.one_lap - 1)) as usize;
345            let lap = tail & !(self.one_lap - 1);
346
347            let new_tail = if index + 1 < N {
348                tail + 1
349            } else {
350                lap.wrapping_add(self.one_lap)
351            };
352
353            // SAFETY: `index < N` by masking invariant.
354            let slot = unsafe { self.buffer.get_unchecked(index).assume_init_ref() };
355            let stamp = slot.stamp_load();
356
357            if tail == stamp {
358                match self.tail.0.compare_exchange_weak(
359                    tail,
360                    new_tail,
361                    Ordering::SeqCst,
362                    Ordering::Relaxed,
363                ) {
364                    Ok(_) => {
365                        // We own the slot: publish value, then stamp (release).
366                        slot.write_value(value);
367                        slot.stamp_store(tail + 1);
368                        return Ok(());
369                    }
370                    Err(t) => {
371                        tail = t;
372                        backoff.spin();
373                    }
374                }
375            } else if stamp.wrapping_add(self.one_lap) == tail + 1 {
376                fence(Ordering::SeqCst);
377                value = f(value, tail, new_tail, slot)?;
378                backoff.spin();
379                tail = self.tail.0.load(Ordering::Relaxed);
380            } else {
381                backoff.snooze();
382                tail = self.tail.0.load(Ordering::Relaxed);
383            }
384        }
385    }
386
387    /// Attempts to push. On full queue, returns the value back as `Err`.
388    pub fn push(&self, value: T) -> Result<(), T> {
389        self.push_or_else(value, |v, tail, _, _| {
390            let head = self.head.0.load(Ordering::Relaxed);
391            if head.wrapping_add(self.one_lap) == tail {
392                Err(v)
393            } else {
394                Ok(v)
395            }
396        })
397    }
398
399    /// Alias of [`Queue::push`] matching the `heapless::mpmc` API.
400    #[inline]
401    pub fn enqueue(&self, value: T) -> Result<(), T> {
402        self.push(value)
403    }
404
405    /// Pushes, replacing the oldest element if full (returns it, else `None`).
406    /// Ring-buffer mode.
407    pub fn force_push(&self, value: T) -> Option<T> {
408        self.push_or_else(value, |v, tail, new_tail, slot| {
409            let head = tail.wrapping_sub(self.one_lap);
410            let new_head = new_tail.wrapping_sub(self.one_lap);
411
412            if self
413                .head
414                .0
415                .compare_exchange_weak(head, new_head, Ordering::SeqCst, Ordering::Relaxed)
416                .is_ok()
417            {
418                self.tail.0.store(new_tail, Ordering::SeqCst);
419                // SAFETY: head moved, slot uniquely ours; swap payload.
420                let old = slot.replace_value(v);
421                slot.stamp_store(tail + 1);
422                Err(old)
423            } else {
424                Ok(v)
425            }
426        })
427        .err()
428    }
429
430    /// Attempts to pop. `None` if empty.
431    pub fn pop(&self) -> Option<T> {
432        let mut backoff = Backoff::new();
433        let mut head = self.head.0.load(Ordering::Relaxed);
434
435        loop {
436            let index = (head & (self.one_lap - 1)) as usize;
437            let lap = head & !(self.one_lap - 1);
438
439            // SAFETY: `index < N` by masking invariant.
440            let slot = unsafe { self.buffer.get_unchecked(index).assume_init_ref() };
441            let stamp = slot.stamp_load();
442
443            if head + 1 == stamp {
444                let new = if index + 1 < N {
445                    head + 1
446                } else {
447                    lap.wrapping_add(self.one_lap)
448                };
449
450                match self.head.0.compare_exchange_weak(
451                    head,
452                    new,
453                    Ordering::SeqCst,
454                    Ordering::Relaxed,
455                ) {
456                    Ok(_) => {
457                        let msg = slot.read_value();
458                        slot.stamp_store(head.wrapping_add(self.one_lap));
459                        return Some(msg);
460                    }
461                    Err(h) => {
462                        head = h;
463                        backoff.spin();
464                    }
465                }
466            } else if stamp == head {
467                fence(Ordering::SeqCst);
468                let tail = self.tail.0.load(Ordering::Relaxed);
469                if tail == head {
470                    return None;
471                }
472                backoff.spin();
473                head = self.head.0.load(Ordering::Relaxed);
474            } else {
475                backoff.snooze();
476                head = self.head.0.load(Ordering::Relaxed);
477            }
478        }
479    }
480
481    /// Alias of [`Queue::pop`] matching the `heapless::mpmc` API.
482    #[inline]
483    pub fn dequeue(&self) -> Option<T> {
484        self.pop()
485    }
486
487    /// `true` if no elements are stored.
488    pub fn is_empty(&self) -> bool {
489        let head = self.head.0.load(Ordering::SeqCst);
490        let tail = self.tail.0.load(Ordering::SeqCst);
491        tail == head
492    }
493
494    /// `true` if no push can succeed without [`Queue::force_push`].
495    pub fn is_full(&self) -> bool {
496        let tail = self.tail.0.load(Ordering::SeqCst);
497        let head = self.head.0.load(Ordering::SeqCst);
498        head.wrapping_add(self.one_lap) == tail
499    }
500
501    /// Number of elements currently stored.
502    pub fn len(&self) -> usize {
503        loop {
504            let tail = self.tail.0.load(Ordering::SeqCst);
505            let head = self.head.0.load(Ordering::SeqCst);
506
507            if self.tail.0.load(Ordering::SeqCst) == tail {
508                let hix = (head & (self.one_lap - 1)) as usize;
509                let tix = (tail & (self.one_lap - 1)) as usize;
510
511                return if hix < tix {
512                    tix - hix
513                } else if hix > tix {
514                    N - hix + tix
515                } else if tail == head {
516                    0
517                } else {
518                    N
519                };
520            }
521        }
522    }
523}
524
525impl<T, const N: usize> Drop for Queue<T, N> {
526    fn drop(&mut self) {
527        if core::mem::needs_drop::<T>() {
528            // Use `load` (not `get_mut`) to read head/tail — works for
529            // both core and loom atomics.
530            let head = self.head.0.load(Ordering::SeqCst);
531            let tail = self.tail.0.load(Ordering::SeqCst);
532
533            let hix = (head & (self.one_lap - 1)) as usize;
534            let tix = (tail & (self.one_lap - 1)) as usize;
535
536            let len = if hix < tix {
537                tix - hix
538            } else if hix > tix {
539                N - hix + tix
540            } else if tail == head {
541                0
542            } else {
543                N
544            };
545
546            for i in 0..len {
547                let index = if hix + i < N { hix + i } else { hix + i - N };
548                // SAFETY: these slots hold live values per head/tail accounting.
549                unsafe {
550                    self.buffer
551                        .get_unchecked_mut(index)
552                        .assume_init_mut()
553                        .drop_value();
554                }
555            }
556        }
557    }
558}
559
560impl<T, const N: usize> fmt::Debug for Queue<T, N> {
561    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
562        f.pad("Queue { .. }")
563    }
564}