#![allow(clippy::missing_errors_doc)]
use core::cell::Cell;
use crate::sched::flynnel_ring_spsc::{
Consumer as SpscConsumer, Producer as SpscProducer, SpscPopResult,
SpscPushResult, new_spsc,
};
#[derive(Debug, PartialEq, Eq)]
pub enum ComposedPushResult<T> {
Ok,
Full(T),
}
impl<T> ComposedPushResult<T> {
#[inline(always)]
pub fn ok(self) -> Option<T> {
match self {
ComposedPushResult::Ok => None,
ComposedPushResult::Full(t) => Some(t),
}
}
#[inline(always)]
pub fn is_ok(&self) -> bool {
matches!(self, ComposedPushResult::Ok)
}
}
#[derive(Debug, PartialEq, Eq)]
pub enum ComposedPopResult<T> {
Ok(T),
Empty,
}
pub struct ComposedMpsc<T: Send> {
pub producers: Vec<SpscProducer<T>>,
pub consumer: ComposedMpscConsumer<T>,
}
pub struct ComposedMpscConsumer<T: Send> {
rings: Vec<SpscConsumer<T>>,
cursor: Cell<usize>,
}
unsafe impl<T: Send> Send for ComposedMpscConsumer<T> {}
pub fn new_composed_mpsc<T: Send>(
n_producers: usize,
capacity_per_producer: usize,
) -> ComposedMpsc<T> {
let n = n_producers.max(1);
let mut producers = Vec::with_capacity(n);
let mut consumers = Vec::with_capacity(n);
for _ in 0..n {
let (p, c) = new_spsc::<T>(capacity_per_producer);
producers.push(p);
consumers.push(c);
}
ComposedMpsc {
producers,
consumer: ComposedMpscConsumer {
rings: consumers,
cursor: Cell::new(0),
},
}
}
impl<T: Send> SpscProducer<T> {
#[inline(always)]
pub fn push_composed(&self, item: T) -> ComposedPushResult<T> {
match self.push(item) {
SpscPushResult::Ok => ComposedPushResult::Ok,
SpscPushResult::Full(t) => ComposedPushResult::Full(t),
}
}
}
impl<T: Send> ComposedMpscConsumer<T> {
#[inline]
pub fn pop(&self) -> ComposedPopResult<T> {
let n = self.rings.len();
if n == 0 {
return ComposedPopResult::Empty;
}
let start = self.cursor.get();
for offset in 0..n {
let idx = (start + offset) % n;
match self.rings[idx].pop() {
SpscPopResult::Ok(item) => {
self.cursor.set((idx + 1) % n);
return ComposedPopResult::Ok(item);
}
SpscPopResult::Empty => continue,
}
}
core::hint::cold_path();
self.cursor.set((start + 1) % n);
ComposedPopResult::Empty
}
#[inline]
pub fn ring_count(&self) -> usize {
self.rings.len()
}
}
#[unsafe(no_mangle)]
pub static __flynnel_marker_ring_composed_push: u8 = 0;
#[unsafe(no_mangle)]
pub static __flynnel_marker_ring_composed_pop: u8 = 0;
#[derive(Debug, PartialEq, Eq)]
pub enum GridPushResult<T> {
Ok,
Full(T),
}
impl<T> GridPushResult<T> {
#[inline(always)]
pub fn ok(self) -> Option<T> {
match self {
GridPushResult::Ok => None,
GridPushResult::Full(t) => Some(t),
}
}
#[inline(always)]
pub fn is_ok(&self) -> bool {
matches!(self, GridPushResult::Ok)
}
}
#[derive(Debug, PartialEq, Eq)]
pub enum GridPopResult<T> {
Ok(T),
Empty,
}
pub struct GridProducer<T: Send> {
handles: Vec<SpscProducer<T>>,
cursor: Cell<usize>,
}
unsafe impl<T: Send> Send for GridProducer<T> {}
impl<T: Send> GridProducer<T> {
#[inline]
pub fn consumer_count(&self) -> usize {
self.handles.len()
}
#[inline]
pub fn push(&self, item: T) -> GridPushResult<T> {
let m = self.handles.len();
if m == 0 {
return GridPushResult::Full(item);
}
let start = self.cursor.get();
let mut carry = item;
for offset in 0..m {
let idx = (start + offset) % m;
match self.handles[idx].push(carry) {
SpscPushResult::Ok => {
self.cursor.set((idx + 1) % m);
return GridPushResult::Ok;
}
SpscPushResult::Full(t) => {
carry = t;
continue;
}
}
}
core::hint::cold_path();
self.cursor.set((start + 1) % m);
GridPushResult::Full(carry)
}
}
pub struct GridConsumer<T: Send> {
handles: Vec<SpscConsumer<T>>,
cursor: Cell<usize>,
}
unsafe impl<T: Send> Send for GridConsumer<T> {}
impl<T: Send> GridConsumer<T> {
#[inline]
pub fn producer_count(&self) -> usize {
self.handles.len()
}
#[inline]
pub fn pop(&self) -> GridPopResult<T> {
let n = self.handles.len();
if n == 0 {
return GridPopResult::Empty;
}
let start = self.cursor.get();
for offset in 0..n {
let idx = (start + offset) % n;
match self.handles[idx].pop() {
SpscPopResult::Ok(item) => {
self.cursor.set((idx + 1) % n);
return GridPopResult::Ok(item);
}
SpscPopResult::Empty => continue,
}
}
core::hint::cold_path();
self.cursor.set((start + 1) % n);
GridPopResult::Empty
}
}
pub struct ComposedMpmc<T: Send> {
pub producers: Vec<GridProducer<T>>,
pub consumers: Vec<GridConsumer<T>>,
}
pub fn new_composed_mpmc<T: Send>(
n_producers: usize,
n_consumers: usize,
capacity_per_pair: usize,
) -> ComposedMpmc<T> {
let n = n_producers.max(1);
let m = n_consumers.max(1);
let mut producer_handles: Vec<Vec<SpscProducer<T>>> =
(0..n).map(|_| Vec::with_capacity(m)).collect();
let mut consumer_handles: Vec<Vec<SpscConsumer<T>>> =
(0..m).map(|_| Vec::with_capacity(n)).collect();
for producer_row in producer_handles.iter_mut() {
for consumer_col in consumer_handles.iter_mut() {
let (p, c) = new_spsc::<T>(capacity_per_pair);
producer_row.push(p);
consumer_col.push(c);
}
}
let producers = producer_handles
.into_iter()
.map(|handles| GridProducer { handles, cursor: Cell::new(0) })
.collect();
let consumers = consumer_handles
.into_iter()
.map(|handles| GridConsumer { handles, cursor: Cell::new(0) })
.collect();
ComposedMpmc { producers, consumers }
}
#[unsafe(no_mangle)]
pub static __flynnel_marker_ring_grid_push: u8 = 0;
#[unsafe(no_mangle)]
pub static __flynnel_marker_ring_grid_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_round_trip_single_producer() {
let composed = new_composed_mpsc::<u32>(1, 8);
let p = &composed.producers[0];
let c = &composed.consumer;
assert!(matches!(p.push_composed(1), ComposedPushResult::Ok));
assert!(matches!(p.push_composed(2), ComposedPushResult::Ok));
assert!(matches!(c.pop(), ComposedPopResult::Ok(1)));
assert!(matches!(c.pop(), ComposedPopResult::Ok(2)));
assert!(matches!(c.pop(), ComposedPopResult::Empty));
}
#[test]
fn round_robin_drains_fairly() {
let composed = new_composed_mpsc::<u32>(3, 8);
let p0 = &composed.producers[0];
let p1 = &composed.producers[1];
let p2 = &composed.producers[2];
let c = &composed.consumer;
p0.push_composed(100).ok();
p1.push_composed(200).ok();
p2.push_composed(300).ok();
assert!(matches!(c.pop(), ComposedPopResult::Ok(100)));
assert!(matches!(c.pop(), ComposedPopResult::Ok(200)));
assert!(matches!(c.pop(), ComposedPopResult::Ok(300)));
assert!(matches!(c.pop(), ComposedPopResult::Empty));
}
#[test]
fn per_producer_fifo_preserved() {
let composed = new_composed_mpsc::<(u32, u32)>(2, 8);
let p0 = &composed.producers[0];
let p1 = &composed.producers[1];
let c = &composed.consumer;
for i in 0..3 {
p0.push_composed((0, i)).ok();
}
for i in 0..3 {
p1.push_composed((1, i)).ok();
}
let mut from_p0 = Vec::new();
let mut from_p1 = Vec::new();
while let ComposedPopResult::Ok((pid, val)) = c.pop() {
match pid {
0 => from_p0.push(val),
1 => from_p1.push(val),
_ => panic!("unexpected pid {pid}"),
}
}
assert_eq!(from_p0, vec![0, 1, 2], "producer 0 FIFO broken");
assert_eq!(from_p1, vec![0, 1, 2], "producer 1 FIFO broken");
}
#[test]
fn full_returns_item_back() {
let composed = new_composed_mpsc::<u32>(2, 2);
let p0 = &composed.producers[0];
assert!(matches!(p0.push_composed(1), ComposedPushResult::Ok));
assert!(matches!(p0.push_composed(2), ComposedPushResult::Ok));
match p0.push_composed(3) {
ComposedPushResult::Full(v) => assert_eq!(v, 3),
_ => panic!("expected Full"),
}
}
#[test]
fn mpmc_grid_single_pair_round_trip() {
let grid = new_composed_mpmc::<u32>(1, 1, 8);
let p = &grid.producers[0];
let c = &grid.consumers[0];
assert!(matches!(p.push(42), GridPushResult::Ok));
assert!(matches!(c.pop(), GridPopResult::Ok(42)));
assert!(matches!(c.pop(), GridPopResult::Empty));
}
#[test]
fn mpmc_grid_producer_round_robins_across_consumers() {
let grid = new_composed_mpmc::<u32>(1, 3, 4);
let p = &grid.producers[0];
p.push(10).ok();
p.push(20).ok();
p.push(30).ok();
assert!(matches!(grid.consumers[0].pop(), GridPopResult::Ok(10)));
assert!(matches!(grid.consumers[1].pop(), GridPopResult::Ok(20)));
assert!(matches!(grid.consumers[2].pop(), GridPopResult::Ok(30)));
assert!(matches!(grid.consumers[0].pop(), GridPopResult::Empty));
}
#[test]
fn mpmc_grid_consumer_round_robins_across_producers() {
let grid = new_composed_mpmc::<u32>(3, 1, 4);
grid.producers[0].push(100).ok();
grid.producers[1].push(200).ok();
grid.producers[2].push(300).ok();
let c = &grid.consumers[0];
assert!(matches!(c.pop(), GridPopResult::Ok(100)));
assert!(matches!(c.pop(), GridPopResult::Ok(200)));
assert!(matches!(c.pop(), GridPopResult::Ok(300)));
assert!(matches!(c.pop(), GridPopResult::Empty));
}
#[test]
fn mpmc_grid_full_returns_item_back() {
let grid = new_composed_mpmc::<u32>(1, 1, 2);
let p = &grid.producers[0];
assert!(p.push(1).is_ok());
assert!(p.push(2).is_ok());
match p.push(3) {
GridPushResult::Full(v) => assert_eq!(v, 3),
_ => panic!("expected Full"),
}
}
#[test]
fn mpmc_grid_4p_4c_concurrent_no_item_loss() {
let n_producers = 4;
let n_consumers = 4;
let n_per_producer = 5_000u32;
let mut grid = new_composed_mpmc::<u32>(n_producers, n_consumers, 64);
let producers = std::mem::take(&mut grid.producers);
let consumers = std::mem::take(&mut grid.consumers);
let total = (n_per_producer as usize) * n_producers;
let consumed = Arc::new(AtomicUsize::new(0));
let sum = Arc::new(AtomicUsize::new(0));
let mut cons_handles = Vec::new();
for c in consumers.into_iter() {
let consumed_c = Arc::clone(&consumed);
let sum_c = Arc::clone(&sum);
cons_handles.push(thread::spawn(move || {
loop {
match c.pop() {
GridPopResult::Ok(v) => {
consumed_c.fetch_add(1, O::Relaxed);
sum_c.fetch_add(v as usize, O::Relaxed);
}
GridPopResult::Empty => {
if consumed_c.load(O::Relaxed) >= total {
break;
}
std::thread::yield_now();
}
}
}
}));
}
let mut prod_handles = Vec::new();
for (p_id, p) in producers.into_iter().enumerate() {
prod_handles.push(thread::spawn(move || {
for i in 0..n_per_producer {
let item = (p_id as u32) * n_per_producer + i;
loop {
match p.push(item) {
GridPushResult::Ok => break,
GridPushResult::Full(_) => std::thread::yield_now(),
}
}
}
}));
}
for h in prod_handles {
h.join().expect("p");
}
for h in cons_handles {
h.join().expect("c");
}
let expected: usize = (0..n_producers as u32)
.flat_map(|p| (0..n_per_producer).map(move |i| (p * n_per_producer + 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 across the grid");
}
#[test]
fn concurrent_4_producers_1_consumer_no_item_loss() {
let n_producers = 4;
let n_per = 10_000u32;
let mut composed = new_composed_mpsc::<u32>(n_producers, 64);
let consumer = composed.consumer;
let producers = std::mem::take(&mut composed.producers);
let total = (n_per as usize) * n_producers;
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 cons = thread::spawn(move || {
while consumed_c.load(O::Relaxed) < total {
match consumer.pop() {
ComposedPopResult::Ok(v) => {
consumed_c.fetch_add(1, O::Relaxed);
sum_c.fetch_add(v as usize, O::Relaxed);
}
ComposedPopResult::Empty => std::thread::yield_now(),
}
}
});
let mut prod_handles = Vec::new();
for (p_id, p) in producers.into_iter().enumerate() {
prod_handles.push(thread::spawn(move || {
for i in 0..n_per {
let item = (p_id as u32) * n_per + i;
loop {
match p.push_composed(item) {
ComposedPushResult::Ok => break,
ComposedPushResult::Full(_) => std::thread::yield_now(),
}
}
}
}));
}
for h in prod_handles {
h.join().expect("p");
}
cons.join().expect("c");
let expected: usize = (0..n_producers as u32)
.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");
}
}