#![allow(clippy::missing_errors_doc)]
use core::cell::UnsafeCell;
use core::mem::MaybeUninit;
use core::sync::atomic::{AtomicI64, AtomicU64, Ordering};
use std::sync::Arc;
#[derive(Debug, PartialEq, Eq)]
pub enum MpscPushResult<T> {
Ok,
Full(T),
}
#[derive(Debug, PartialEq, Eq)]
pub enum MpscPopResult<T> {
Ok(T),
Empty,
}
#[repr(C, align(64))]
struct MpscSlot<T> {
seq: AtomicU64,
data: UnsafeCell<MaybeUninit<T>>,
}
#[repr(C, align(64))]
struct MpscHeader<T> {
tail: AtomicI64,
_pad_tail: [u8; 56],
head: AtomicI64,
_pad_head: [u8; 56],
capacity: usize,
capacity_mask: i64,
buffer: Box<[MpscSlot<T>]>,
}
unsafe impl<T: Send> Send for MpscHeader<T> {}
unsafe impl<T: Send> Sync for MpscHeader<T> {}
pub struct MpscProducer<T> {
inner: Arc<MpscHeader<T>>,
}
impl<T> Clone for MpscProducer<T> {
fn clone(&self) -> Self {
Self {
inner: Arc::clone(&self.inner),
}
}
}
pub struct MpscConsumer<T> {
inner: Arc<MpscHeader<T>>,
}
unsafe impl<T: Send> Send for MpscConsumer<T> {}
pub fn new_mpsc<T: Send>(capacity: usize) -> (MpscProducer<T>, MpscConsumer<T>) {
let capacity = capacity.max(2).next_power_of_two();
let mut buf = Vec::with_capacity(capacity);
for i in 0..capacity {
buf.push(MpscSlot {
seq: AtomicU64::new(i as u64),
data: UnsafeCell::new(MaybeUninit::uninit()),
});
}
let inner = Arc::new(MpscHeader {
tail: AtomicI64::new(0),
_pad_tail: [0u8; 56],
head: AtomicI64::new(0),
_pad_head: [0u8; 56],
capacity,
capacity_mask: (capacity as i64) - 1,
buffer: buf.into_boxed_slice(),
});
(
MpscProducer {
inner: Arc::clone(&inner),
},
MpscConsumer { inner },
)
}
impl<T: Send> MpscProducer<T> {
#[inline]
pub fn push(&self, item: T) -> MpscPushResult<T> {
let h = &*self.inner;
let mut pos = h.tail.load(Ordering::Relaxed);
loop {
let slot = unsafe { h.buffer.get_unchecked((pos & h.capacity_mask) as usize) };
let seq = slot.seq.load(Ordering::Acquire);
let diff = (seq as i64) - pos;
if diff == 0 {
match h.tail.compare_exchange_weak(
pos,
pos + 1,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => {
unsafe {
(*slot.data.get()).write(item);
}
slot.seq.store((pos as u64) + 1, Ordering::Release);
return MpscPushResult::Ok;
}
Err(new_pos) => {
pos = new_pos;
continue;
}
}
} else if diff < 0 {
core::hint::cold_path();
return MpscPushResult::Full(item);
} else {
core::hint::cold_path();
pos = h.tail.load(Ordering::Relaxed);
}
}
}
}
impl<T: Send> MpscConsumer<T> {
#[inline]
pub fn pop(&self) -> MpscPopResult<T> {
let h = &*self.inner;
let pos = h.head.load(Ordering::Relaxed);
let slot = unsafe { h.buffer.get_unchecked((pos & h.capacity_mask) as usize) };
let seq = slot.seq.load(Ordering::Acquire);
let diff = (seq as i64) - (pos + 1);
if diff != 0 {
core::hint::cold_path();
return MpscPopResult::Empty;
}
let item = unsafe { (*slot.data.get()).assume_init_read() };
slot.seq.store(
(pos as u64) + (h.capacity as u64),
Ordering::Release,
);
h.head.store(pos + 1, Ordering::Relaxed);
MpscPopResult::Ok(item)
}
}
impl<T> Drop for MpscHeader<T> {
fn drop(&mut self) {
let t = self.tail.load(Ordering::Relaxed);
let h = self.head.load(Ordering::Relaxed);
let mut pos = h;
while pos < t {
let slot = &self.buffer[(pos & self.capacity_mask) as usize];
let seq = slot.seq.load(Ordering::Relaxed);
if seq as i64 == pos + 1 {
unsafe {
(*slot.data.get()).assume_init_drop();
}
}
pos += 1;
}
}
}
#[unsafe(no_mangle)]
pub static __flynnel_marker_ring_mpsc_push: u8 = 0;
#[unsafe(no_mangle)]
pub static __flynnel_marker_ring_mpsc_pop: u8 = 0;
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering as O};
use std::thread;
#[test]
fn push_pop_single_thread() {
let (p, c) = new_mpsc::<u32>(8);
assert!(matches!(p.push(1), MpscPushResult::Ok));
assert!(matches!(p.push(2), MpscPushResult::Ok));
assert!(matches!(p.push(3), MpscPushResult::Ok));
assert!(matches!(c.pop(), MpscPopResult::Ok(1)));
assert!(matches!(c.pop(), MpscPopResult::Ok(2)));
assert!(matches!(c.pop(), MpscPopResult::Ok(3)));
assert!(matches!(c.pop(), MpscPopResult::Empty));
}
#[test]
fn full_returns_item_back() {
let (p, _c) = new_mpsc::<u32>(2);
assert!(matches!(p.push(1), MpscPushResult::Ok));
assert!(matches!(p.push(2), MpscPushResult::Ok));
match p.push(3) {
MpscPushResult::Full(v) => assert_eq!(v, 3),
_ => panic!("expected Full"),
}
}
#[test]
fn drop_runs_destructors_for_unclaimed_slots() {
struct DropCount<'a>(&'a AtomicUsize);
impl Drop for DropCount<'_> {
fn drop(&mut self) {
self.0.fetch_add(1, O::Relaxed);
}
}
let count = AtomicUsize::new(0);
{
let (p, _c) = new_mpsc::<DropCount<'_>>(4);
assert!(matches!(p.push(DropCount(&count)), MpscPushResult::Ok));
assert!(matches!(p.push(DropCount(&count)), MpscPushResult::Ok));
assert!(matches!(p.push(DropCount(&count)), MpscPushResult::Ok));
}
assert_eq!(count.load(O::Relaxed), 3);
}
#[test]
fn concurrent_mpsc_stress_no_item_loss() {
let (p_proto, c) = new_mpsc::<u32>(64);
let n_per = 5_000u32;
let n_producers = 4u32;
let total = (n_per * n_producers) as usize;
let consumed = Arc::new(AtomicUsize::new(0));
let sum = Arc::new(AtomicUsize::new(0));
let consumed_c = Arc::clone(&consumed);
let sum_c = Arc::clone(&sum);
let consumer = thread::spawn(move || {
while consumed_c.load(O::Relaxed) < total {
match c.pop() {
MpscPopResult::Ok(v) => {
consumed_c.fetch_add(1, O::Relaxed);
sum_c.fetch_add(v as usize, O::Relaxed);
}
MpscPopResult::Empty => std::thread::yield_now(),
}
}
});
let mut producers = Vec::new();
for p_id in 0..n_producers {
let p = p_proto.clone();
producers.push(thread::spawn(move || {
for i in 0..n_per {
let item = p_id * n_per + i;
loop {
match p.push(item) {
MpscPushResult::Ok => break,
MpscPushResult::Full(_) => std::thread::yield_now(),
}
}
}
}));
}
for h in producers {
h.join().expect("p");
}
consumer.join().expect("c");
let expected: usize = (0..n_producers)
.flat_map(|p| (0..n_per).map(move |i| (p * n_per + i) as usize))
.sum();
assert_eq!(consumed.load(O::Relaxed), total);
assert_eq!(sum.load(O::Relaxed), expected,
"sum invariant: each pushed item consumed exactly once");
}
}