#![allow(clippy::missing_errors_doc)]
use core::sync::atomic::{AtomicBool, AtomicUsize, Ordering, fence};
use std::sync::{Arc, OnceLock};
use crate::sched::flynnel_ring::{FlynnelRing, PopResult, PushResult};
use crate::sched::sleep::Parker;
#[derive(Debug, PartialEq, Eq)]
pub enum NotifySendResult<T> {
Ok,
Closed(T),
}
impl<T> NotifySendResult<T> {
#[inline]
pub fn is_ok(&self) -> bool {
matches!(self, NotifySendResult::Ok)
}
#[inline]
pub fn err(self) -> Option<T> {
match self {
NotifySendResult::Ok => None,
NotifySendResult::Closed(t) => Some(t),
}
}
}
#[derive(Debug, PartialEq, Eq)]
pub enum NotifyTrySendResult<T> {
Ok,
Full(T),
Closed(T),
}
struct NotifyInner<T: Send> {
ring: FlynnelRing<T>,
parker_slots: Box<[OnceLock<Arc<Parker>>]>,
idle: Box<[AtomicBool]>,
idle_count: AtomicUsize,
register_next: AtomicUsize,
next_wake: AtomicUsize,
shutdown: AtomicBool,
}
pub struct NotifyHub<T: Send> {
inner: Arc<NotifyInner<T>>,
}
impl<T: Send> NotifyHub<T> {
pub fn new(capacity: usize, n_consumers: usize) -> Self {
let n = n_consumers.max(1);
let slots: Vec<OnceLock<Arc<Parker>>> =
(0..n).map(|_| OnceLock::new()).collect();
let idle: Vec<AtomicBool> = (0..n).map(|_| AtomicBool::new(false)).collect();
Self {
inner: Arc::new(NotifyInner {
ring: FlynnelRing::new(capacity),
parker_slots: slots.into_boxed_slice(),
idle: idle.into_boxed_slice(),
idle_count: AtomicUsize::new(0),
register_next: AtomicUsize::new(0),
next_wake: AtomicUsize::new(0),
shutdown: AtomicBool::new(false),
}),
}
}
pub fn sender(&self) -> NotifySender<T> {
NotifySender { inner: Arc::clone(&self.inner) }
}
pub fn register_consumer(&self) -> NotifyReceiver<T> {
const RECV_SPIN_ROUNDS: u32 = 8;
let parker = Arc::new(Parker::new(RECV_SPIN_ROUNDS));
let n = self.inner.parker_slots.len();
let raw = self.inner.register_next.fetch_add(1, Ordering::Relaxed);
let idx = raw % n;
let slot = self.inner.parker_slots[idx]
.set(Arc::clone(&parker))
.is_ok()
.then_some(idx);
NotifyReceiver {
inner: Arc::clone(&self.inner),
parker,
slot,
}
}
pub fn shutdown(&self) {
self.inner.shutdown.store(true, Ordering::Release);
wake_all(&self.inner);
}
pub fn len(&self) -> usize {
self.inner.ring.len()
}
pub fn is_empty(&self) -> bool {
self.inner.ring.is_empty()
}
}
impl<T: Send> Clone for NotifyHub<T> {
fn clone(&self) -> Self {
Self { inner: Arc::clone(&self.inner) }
}
}
pub struct NotifyShutdownOnDrop<T: Send> {
hub: NotifyHub<T>,
}
impl<T: Send> Drop for NotifyShutdownOnDrop<T> {
fn drop(&mut self) {
self.hub.inner.shutdown.store(true, Ordering::Release);
wake_all(&self.hub.inner);
}
}
impl<T: Send> NotifyHub<T> {
pub fn shutdown_on_drop(self) -> NotifyShutdownOnDrop<T> {
NotifyShutdownOnDrop { hub: self }
}
}
pub struct NotifySender<T: Send> {
inner: Arc<NotifyInner<T>>,
}
impl<T: Send> Clone for NotifySender<T> {
fn clone(&self) -> Self {
Self { inner: Arc::clone(&self.inner) }
}
}
impl<T: Send> NotifySender<T> {
#[inline]
pub fn send(&self, mut item: T) -> NotifySendResult<T> {
if self.inner.shutdown.load(Ordering::Acquire) {
return NotifySendResult::Closed(item);
}
loop {
match self.inner.ring.push(item) {
PushResult::Ok => {
wake_one(&self.inner);
return NotifySendResult::Ok;
}
PushResult::Full(t) => {
if self.inner.shutdown.load(Ordering::Acquire) {
return NotifySendResult::Closed(t);
}
item = t;
core::hint::spin_loop();
}
}
}
}
#[inline]
pub fn try_send(&self, item: T) -> NotifyTrySendResult<T> {
if self.inner.shutdown.load(Ordering::Acquire) {
return NotifyTrySendResult::Closed(item);
}
match self.inner.ring.push(item) {
PushResult::Ok => {
wake_one(&self.inner);
NotifyTrySendResult::Ok
}
PushResult::Full(t) => NotifyTrySendResult::Full(t),
}
}
pub fn shutdown(&self) {
self.inner.shutdown.store(true, Ordering::Release);
wake_all(&self.inner);
}
pub fn is_empty(&self) -> bool {
self.inner.ring.is_empty()
}
}
pub struct NotifyReceiver<T: Send> {
inner: Arc<NotifyInner<T>>,
parker: Arc<Parker>,
slot: Option<usize>,
}
impl<T: Send> NotifyReceiver<T> {
pub fn recv(&self) -> Option<T> {
let announced = self.slot.filter(|_| self.inner.idle.len() > 1);
loop {
match self.inner.ring.pop() {
PopResult::Ok(t) => return Some(t),
PopResult::Empty => {
if self.inner.shutdown.load(Ordering::Acquire) {
if let PopResult::Ok(t) = self.inner.ring.pop() {
return Some(t);
}
return None;
}
let inner = &self.inner;
if let Some(slot) = announced {
inner.announce_idle(slot);
}
let ready = self.parker.park_until(|| {
!inner.ring.is_empty() || inner.shutdown.load(Ordering::Acquire)
});
if let Some(slot) = announced {
inner.withdraw_idle(slot);
}
if !ready {
if let PopResult::Ok(t) = self.inner.ring.pop() {
return Some(t);
}
return None;
}
}
}
}
}
#[inline]
pub fn try_recv(&self) -> Option<T> {
match self.inner.ring.pop() {
PopResult::Ok(t) => Some(t),
PopResult::Empty => None,
}
}
}
impl<T: Send> NotifyInner<T> {
#[inline]
fn announce_idle(&self, slot: usize) {
self.idle_count.fetch_add(1, Ordering::Relaxed);
self.idle[slot].store(true, Ordering::Release);
fence(Ordering::SeqCst);
}
#[inline]
fn withdraw_idle(&self, slot: usize) {
if self.idle[slot].swap(false, Ordering::AcqRel) {
self.idle_count.fetch_sub(1, Ordering::Relaxed);
}
}
}
#[inline]
fn wake_one<T: Send>(inner: &Arc<NotifyInner<T>>) {
let n = inner.parker_slots.len();
if n == 0 {
return;
}
if n == 1 {
if let Some(p) = inner.parker_slots[0].get() {
p.unpark();
}
return;
}
fence(Ordering::SeqCst);
if inner.idle_count.load(Ordering::Relaxed) == 0 {
return;
}
let start = inner.next_wake.fetch_add(1, Ordering::Relaxed) % n;
for offset in 0..n {
let idx = (start + offset) % n;
let flag = &inner.idle[idx];
if flag.load(Ordering::Relaxed) && flag.swap(false, Ordering::AcqRel) {
inner.idle_count.fetch_sub(1, Ordering::Relaxed);
if let Some(p) = inner.parker_slots[idx].get() {
p.unpark();
}
return;
}
}
}
#[inline]
fn wake_all<T: Send>(inner: &Arc<NotifyInner<T>>) {
for slot in inner.parker_slots.iter() {
if let Some(p) = slot.get() {
p.unpark();
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering as O};
use std::thread;
use std::time::Duration;
#[test]
fn single_send_single_recv_round_trip() {
let hub = NotifyHub::<u32>::new(8, 1);
let tx = hub.sender();
let hub2 = hub.clone();
let cons = thread::spawn(move || {
let rx = hub2.register_consumer();
rx.recv()
});
thread::sleep(Duration::from_millis(20));
assert!(tx.send(42).is_ok());
assert_eq!(cons.join().expect("consumer"), Some(42));
}
#[test]
fn shutdown_returns_none_after_drain() {
let hub = NotifyHub::<u32>::new(8, 1);
let tx = hub.sender();
let hub2 = hub.clone();
let cons = thread::spawn(move || {
let rx = hub2.register_consumer();
let a = rx.recv();
let b = rx.recv();
let c = rx.recv();
(a, b, c)
});
thread::sleep(Duration::from_millis(20));
assert!(tx.send(1).is_ok());
assert!(tx.send(2).is_ok());
hub.shutdown();
let (a, b, c) = cons.join().expect("consumer");
assert_eq!(a, Some(1));
assert_eq!(b, Some(2));
assert_eq!(c, None, "third recv after shutdown returns None");
}
#[test]
fn mpmc_round_trip_4p_4c() {
let hub = NotifyHub::<u32>::new(64, 4);
let total = 4000usize;
let n_producers = 4;
let n_consumers = 4;
let per_producer = (total / n_producers) as u32;
let consumed = Arc::new(AtomicUsize::new(0));
let sum = Arc::new(AtomicUsize::new(0));
let mut cons_handles = Vec::new();
for _ in 0..n_consumers {
let hub2 = hub.clone();
let consumed = Arc::clone(&consumed);
let sum = Arc::clone(&sum);
cons_handles.push(thread::spawn(move || {
let rx = hub2.register_consumer();
while let Some(v) = rx.recv() {
consumed.fetch_add(1, O::Relaxed);
sum.fetch_add(v as usize, O::Relaxed);
}
}));
}
thread::sleep(Duration::from_millis(20));
let mut prod_handles = Vec::new();
for p in 0..n_producers {
let tx = hub.sender();
prod_handles.push(thread::spawn(move || {
for i in 0..per_producer {
let v = (p as u32) * per_producer + i;
while !tx.send(v).is_ok() {}
}
}));
}
for h in prod_handles {
h.join().expect("p");
}
for _ in 0..200 {
if consumed.load(O::Relaxed) >= total {
break;
}
thread::sleep(Duration::from_millis(10));
}
hub.shutdown();
for h in cons_handles {
h.join().expect("c");
}
let expected: usize = (0..total).map(|i| i as u32 as usize).sum();
assert_eq!(consumed.load(O::Relaxed), total);
assert_eq!(sum.load(O::Relaxed), expected,
"sum invariant: every pushed value consumed exactly once");
}
#[test]
#[ignore = "stages a stranded item; run by hand"]
fn a_wake_on_a_busy_consumer_still_reaches_a_parked_one() {
use std::sync::atomic::AtomicBool;
use std::time::Instant;
const ATTEMPTS: usize = 20;
let bound = Duration::from_secs(2);
for attempt in 1..=ATTEMPTS {
let hub = NotifyHub::<u32>::new(8, 2);
let tx = hub.sender();
let a_got = Arc::new(AtomicUsize::new(0));
let b_got = Arc::new(AtomicUsize::new(0));
let registered = Arc::new(AtomicUsize::new(0));
let release = Arc::new(AtomicBool::new(false));
let a = {
let hub = hub.clone();
let (got, registered) = (Arc::clone(&a_got), Arc::clone(®istered));
thread::spawn(move || {
let rx = hub.register_consumer();
registered.fetch_add(1, O::SeqCst);
if let Some(v) = rx.recv() {
got.store(v as usize, O::SeqCst);
}
})
};
while registered.load(O::SeqCst) < 1 {
thread::yield_now();
}
let b = {
let hub = hub.clone();
let (got, registered, release) = (
Arc::clone(&b_got),
Arc::clone(®istered),
Arc::clone(&release),
);
thread::spawn(move || {
let rx = hub.register_consumer();
registered.fetch_add(1, O::SeqCst);
loop {
if let Some(v) = rx.try_recv() {
got.store(v as usize, O::SeqCst);
break;
}
if release.load(O::SeqCst) {
return;
}
std::hint::spin_loop();
}
while !release.load(O::SeqCst) {
thread::sleep(Duration::from_millis(1));
}
})
};
while registered.load(O::SeqCst) < 2 {
thread::yield_now();
}
thread::sleep(Duration::from_millis(100));
assert!(tx.send(1).is_ok());
let start = Instant::now();
while a_got.load(O::SeqCst) == 0
&& b_got.load(O::SeqCst) == 0
&& start.elapsed() < bound
{
thread::yield_now();
}
let staged = b_got.load(O::SeqCst) == 1 && a_got.load(O::SeqCst) == 0;
if staged {
thread::sleep(Duration::from_millis(100));
assert!(tx.send(2).is_ok());
let start = Instant::now();
while a_got.load(O::SeqCst) == 0 && start.elapsed() < bound {
thread::sleep(Duration::from_millis(1));
}
}
let reached = a_got.load(O::SeqCst) == 2;
release.store(true, O::SeqCst);
hub.shutdown();
a.join().expect("consumer a");
b.join().expect("consumer b");
if staged {
println!(
"STRAND hub attempt={attempt} second_item_reached_parked_consumer={reached} bound_ms={}",
bound.as_millis()
);
assert!(
reached,
"the second item stayed queued while consumer A slept, its wake spent on busy consumer B"
);
return;
}
}
panic!(
"in {ATTEMPTS} attempts the woken consumer always won the first item, so the interleaving was never staged"
);
}
}