#![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 PushResult<T> {
Ok,
Full(T),
}
#[derive(Debug, PartialEq, Eq)]
pub enum PopResult<T> {
Ok(T),
Empty,
}
#[repr(C, align(64))]
struct Slot<T> {
seq: AtomicU64,
data: UnsafeCell<MaybeUninit<T>>,
}
#[repr(C, align(64))]
struct Header<T> {
tail: AtomicI64,
_pad_tail: [u8; 56],
head: AtomicI64,
_pad_head: [u8; 56],
capacity: usize,
capacity_mask: i64,
buffer: Box<[Slot<T>]>,
}
unsafe impl<T: Send> Send for Header<T> {}
unsafe impl<T: Send> Sync for Header<T> {}
pub struct FlynnelRing<T> {
inner: Arc<Header<T>>,
}
impl<T> Clone for FlynnelRing<T> {
fn clone(&self) -> Self {
Self {
inner: Arc::clone(&self.inner),
}
}
}
impl<T: Send> FlynnelRing<T> {
pub fn new(capacity: usize) -> Self {
let capacity = capacity.max(2).next_power_of_two();
let mut buf = Vec::with_capacity(capacity);
for i in 0..capacity {
buf.push(Slot {
seq: AtomicU64::new(i as u64),
data: UnsafeCell::new(MaybeUninit::uninit()),
});
}
let inner = Arc::new(Header {
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(),
});
Self { inner }
}
#[inline]
pub fn capacity(&self) -> usize {
self.inner.capacity
}
#[inline]
pub fn len(&self) -> usize {
let h = &*self.inner;
let t = h.tail.load(Ordering::Acquire);
let h2 = h.head.load(Ordering::Acquire);
(t - h2).max(0) as usize
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[inline]
pub fn push(&self, item: T) -> PushResult<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 PushResult::Ok;
}
Err(new_pos) => {
pos = new_pos;
continue;
}
}
} else if diff < 0 {
core::hint::cold_path();
return PushResult::Full(item);
} else {
core::hint::cold_path();
pos = h.tail.load(Ordering::Relaxed);
}
}
}
#[inline]
pub fn push_blocking(&self, item: T) {
let h = &*self.inner;
let pos = h.tail.fetch_add(1, Ordering::Relaxed);
let slot = unsafe { h.buffer.get_unchecked((pos & h.capacity_mask) as usize) };
loop {
let seq = slot.seq.load(Ordering::Acquire);
if (seq as i64) == pos {
break;
}
core::hint::spin_loop();
}
unsafe {
(*slot.data.get()).write(item);
}
slot.seq.store((pos as u64) + 1, Ordering::Release);
}
#[inline]
pub fn pop_blocking(&self) -> T {
let h = &*self.inner;
let pos = h.head.fetch_add(1, Ordering::Relaxed);
let slot = unsafe { h.buffer.get_unchecked((pos & h.capacity_mask) as usize) };
loop {
let seq = slot.seq.load(Ordering::Acquire);
if (seq as i64) == pos + 1 {
break;
}
core::hint::spin_loop();
}
let item = unsafe { (*slot.data.get()).assume_init_read() };
slot.seq.store(
(pos as u64) + (h.capacity as u64),
Ordering::Release,
);
item
}
#[inline]
pub fn pop(&self) -> PopResult<T> {
let h = &*self.inner;
let mut pos = h.head.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 + 1);
if diff == 0 {
match h.head.compare_exchange_weak(
pos,
pos + 1,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => {
let item = unsafe { (*slot.data.get()).assume_init_read() };
slot.seq.store(
(pos as u64) + (h.capacity as u64),
Ordering::Release,
);
return PopResult::Ok(item);
}
Err(new_pos) => {
pos = new_pos;
continue;
}
}
} else if diff < 0 {
core::hint::cold_path();
return PopResult::Empty;
} else {
core::hint::cold_path();
pos = h.head.load(Ordering::Relaxed);
}
}
}
}
impl<T> Drop for Header<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_push: u8 = 0;
#[unsafe(no_mangle)]
pub static __flynnel_marker_ring_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_threaded() {
let r = FlynnelRing::<u32>::new(8);
assert!(matches!(r.push(1), PushResult::Ok));
assert!(matches!(r.push(2), PushResult::Ok));
assert!(matches!(r.push(3), PushResult::Ok));
assert!(matches!(r.pop(), PopResult::Ok(1)));
assert!(matches!(r.pop(), PopResult::Ok(2)));
assert!(matches!(r.pop(), PopResult::Ok(3)));
assert!(matches!(r.pop(), PopResult::Empty));
}
#[test]
fn capacity_rounds_to_power_of_two() {
let r = FlynnelRing::<u32>::new(5);
assert_eq!(r.capacity(), 8);
let r0 = FlynnelRing::<u32>::new(0);
assert_eq!(r0.capacity(), 2);
}
#[test]
fn full_returns_item_back() {
let r = FlynnelRing::<u32>::new(2);
assert!(matches!(r.push(1), PushResult::Ok));
assert!(matches!(r.push(2), PushResult::Ok));
match r.push(3) {
PushResult::Full(v) => assert_eq!(v, 3),
_ => panic!("expected Full"),
}
}
#[test]
fn empty_pop_returns_empty() {
let r = FlynnelRing::<u32>::new(4);
assert!(matches!(r.pop(), PopResult::Empty));
}
#[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 r = FlynnelRing::<DropCount<'_>>::new(4);
assert!(matches!(r.push(DropCount(&count)), PushResult::Ok));
assert!(matches!(r.push(DropCount(&count)), PushResult::Ok));
assert!(matches!(r.push(DropCount(&count)), PushResult::Ok));
}
assert_eq!(count.load(O::Relaxed), 3);
}
#[test]
fn concurrent_mpmc_stress_no_item_loss() {
let r = Arc::new(FlynnelRing::<u32>::new(64));
let n = 5_000u32;
let produced = Arc::new(AtomicUsize::new(0));
let consumed = Arc::new(AtomicUsize::new(0));
let sum_consumed = Arc::new(AtomicUsize::new(0));
let mut producers = Vec::new();
for p_id in 0..4u32 {
let r = Arc::clone(&r);
let produced = Arc::clone(&produced);
let n_per = n / 4;
producers.push(thread::spawn(move || {
for i in 0..n_per {
let item = p_id * n_per + i;
loop {
match r.push(item) {
PushResult::Ok => {
produced.fetch_add(1, O::Relaxed);
break;
}
PushResult::Full(_) => {
std::thread::yield_now();
}
}
}
}
}));
}
let mut consumers = Vec::new();
for _ in 0..4 {
let r = Arc::clone(&r);
let consumed = Arc::clone(&consumed);
let sum_consumed = Arc::clone(&sum_consumed);
consumers.push(thread::spawn(move || {
while consumed.load(O::Relaxed) < n as usize {
match r.pop() {
PopResult::Ok(v) => {
consumed.fetch_add(1, O::Relaxed);
sum_consumed.fetch_add(v as usize, O::Relaxed);
}
PopResult::Empty => std::thread::yield_now(),
}
}
}));
}
for h in producers {
h.join().expect("producer");
}
for h in consumers {
h.join().expect("consumer");
}
let n_per = n / 4;
let expected: usize = (0..4u32)
.flat_map(|p| (0..n_per).map(move |i| (p * n_per + i) as usize))
.sum();
assert_eq!(consumed.load(O::Relaxed), n as usize);
assert_eq!(sum_consumed.load(O::Relaxed), expected,
"sum invariant: each pushed item must be consumed exactly once");
}
}