use core::{num::NonZeroUsize, time::Duration};
use std::{
collections::BTreeMap,
panic::AssertUnwindSafe,
sync::{
Arc,
atomic::{AtomicBool, AtomicUsize, Ordering},
},
thread::{self, ThreadId},
time::Instant,
};
use super::{Bench, Crew, CrewOptions, DEFAULT_LABEL, HashRouter, Router};
use crate::conduit::{self, park_on};
const PATIENCE: Duration = Duration::from_secs(10);
const HELD: Duration = Duration::from_millis(150);
fn seats(workers: usize, queue: usize, returns: usize) -> CrewOptions {
CrewOptions::new()
.with_workers(NonZeroUsize::new(workers).expect("not zero"))
.with_queue_depth(NonZeroUsize::new(queue).expect("not zero"))
.with_return_depth(NonZeroUsize::new(returns).expect("not zero"))
}
struct ToZero;
impl<K: ?Sized> Router<K> for ToZero {
fn route(&self, _: &K) -> u64 {
0
}
}
struct Ledger {
index: usize,
}
impl Bench for Ledger {
type Task = (u64, u64);
type Yield = (usize, u64, u64);
fn work(&mut self, (key, seq): (u64, u64)) -> impl IntoIterator<Item = (usize, u64, u64)> {
[(self.index, key, seq)]
}
}
fn interleaved(options: CrewOptions) -> Vec<(usize, u64, u64)> {
let crew =
Crew::spawn(options, HashRouter::new(), |index| Ledger { index }).expect("the crew spawns");
let mut harvested = Vec::new();
for seq in 0..6 {
for key in 0..4 {
crew.route(&key, (key, seq)).expect("the crew is alive");
harvested.extend(crew.harvest());
}
}
harvested.extend(crew.close());
harvested
}
fn per_key(results: &[(usize, u64, u64)]) -> BTreeMap<u64, Vec<u64>> {
let mut grouped: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
for &(_, key, seq) in results {
grouped.entry(key).or_default().push(seq);
}
grouped
}
#[test]
fn one_key_reaches_one_bench_and_keeps_its_order() {
let results = interleaved(seats(4, 4, 64));
assert_eq!(results.len(), 24, "nothing was lost");
let mut bench_of: BTreeMap<u64, usize> = BTreeMap::new();
for &(worker, key, _) in &results {
let claimed = *bench_of.entry(key).or_insert(worker);
assert_eq!(claimed, worker, "key {key} reached two benches");
}
assert_eq!(
per_key(&results),
BTreeMap::from([
(0, vec![0, 1, 2, 3, 4, 5]),
(1, vec![0, 1, 2, 3, 4, 5]),
(2, vec![0, 1, 2, 3, 4, 5]),
(3, vec![0, 1, 2, 3, 4, 5]),
])
);
}
#[test]
fn the_two_forms_answer_the_same_per_key_sequences() {
let inline = interleaved(seats(1, 4, 64));
let pool = interleaved(seats(4, 4, 64));
assert_eq!(inline.len(), pool.len());
assert_eq!(
per_key(&inline),
per_key(&pool),
"the width changes who does the work and not what comes out of it"
);
}
struct Whose;
impl Bench for Whose {
type Task = ();
type Yield = (ThreadId, Option<String>);
fn work(&mut self, (): ()) -> impl IntoIterator<Item = (ThreadId, Option<String>)> {
let here = thread::current();
[(here.id(), here.name().map(str::to_owned))]
}
}
#[test]
fn the_inline_form_runs_on_the_calling_thread() {
let crew = Crew::spawn(seats(1, 4, 8), ToZero, |_| Whose).expect("the crew spawns");
assert!(crew.is_inline());
assert_eq!(crew.workers().get(), 1);
crew.route(&(), ()).expect("the crew is alive");
let ran: Vec<_> = crew.close().collect();
assert_eq!(ran.len(), 1);
assert_eq!(
ran[0].0,
thread::current().id(),
"the inline form spawned a thread"
);
assert_ne!(
ran[0].1.as_deref(),
Some(DEFAULT_LABEL),
"no worker thread was named"
);
}
#[test]
fn the_pool_form_runs_on_threads_of_its_own() {
let crew = Crew::spawn(seats(3, 4, 8), HashRouter::new(), |_| Whose).expect("the crew spawns");
assert!(!crew.is_inline());
for key in 0..12u64 {
crew.route(&key, ()).expect("the crew is alive");
}
let ran: Vec<_> = crew.close().collect();
assert_eq!(ran.len(), 12);
let here = thread::current().id();
for (id, name) in &ran {
assert_ne!(*id, here, "a worker ran on the calling thread");
assert!(
name
.as_deref()
.is_some_and(|name| name.starts_with(DEFAULT_LABEL)),
"a worker thread went unnamed: {name:?}"
);
}
}
#[test]
fn the_inline_form_s_arm_parks_rather_than_closing() {
let crew = Crew::spawn(seats(1, 4, 8), ToZero, |_| Whose).expect("the crew spawns");
crew.route(&(), ()).expect("the crew is alive");
assert_eq!(crew.pending(), 1);
assert!(
park_on(crew.returns().arm(true, || ()), Duration::from_millis(100)).is_none(),
"the inline form's arm answered on a line nothing speaks on"
);
assert_eq!(crew.harvest().count(), 1);
}
#[test]
fn the_pool_form_s_arm_fires_and_leaves_the_order_alone() {
let crew = Crew::spawn(seats(2, 4, 8), ToZero, |_| Whose).expect("the crew spawns");
crew.route(&(), ()).expect("the crew is alive");
assert!(
park_on(crew.returns().arm(true, || "spoke"), PATIENCE)
.is_some_and(|heard| heard == Some("spoke")),
"the crew never spoke"
);
assert_eq!(crew.harvest().count(), 1, "the arm swallowed the result");
}
struct Gated {
gate: conduit::Receiver<()>,
}
impl Bench for Gated {
type Task = u64;
type Yield = u64;
fn work(&mut self, task: u64) -> impl IntoIterator<Item = u64> {
let _ = self.gate.recv();
[task]
}
}
#[test]
fn a_full_in_queue_makes_route_wait() {
let (open, gate) = conduit::bounded::<()>(16);
let crew = Crew::spawn(seats(2, 1, 16), ToZero, |_| Gated { gate: gate.clone() })
.expect("the crew spawns");
let releasing = thread::spawn(move || {
thread::sleep(HELD);
for _ in 0..8 {
let _ = open.send(());
}
});
let began = Instant::now();
for task in 0..3 {
crew.route(&(), task).expect("the crew is alive");
}
let waited = began.elapsed();
releasing.join().expect("the releasing thread");
drop(crew.close());
assert!(
waited >= HELD / 2,
"routing three tasks into a queue of one never waited: {waited:?}"
);
}
#[test]
fn a_deep_in_queue_does_not_make_route_wait() {
let (open, gate) = conduit::bounded::<()>(16);
let crew = Crew::spawn(seats(2, 8, 16), ToZero, |_| Gated { gate: gate.clone() })
.expect("the crew spawns");
let began = Instant::now();
for task in 0..3 {
crew.route(&(), task).expect("the crew is alive");
}
let waited = began.elapsed();
for _ in 0..8 {
let _ = open.send(());
}
drop(crew.close());
assert!(
waited < HELD / 2,
"a queue with room still waited: {waited:?}"
);
}
struct Spilling {
made: Arc<AtomicUsize>,
each: usize,
}
struct Spill {
made: Arc<AtomicUsize>,
left: usize,
}
impl Iterator for Spill {
type Item = usize;
fn next(&mut self) -> Option<usize> {
if self.left == 0 {
return None;
}
self.left -= 1;
Some(self.made.fetch_add(1, Ordering::SeqCst))
}
}
impl Bench for Spilling {
type Task = ();
type Yield = usize;
fn work(&mut self, (): ()) -> impl IntoIterator<Item = usize> {
Spill {
made: Arc::clone(&self.made),
left: self.each,
}
}
}
#[test]
fn a_full_return_line_makes_a_worker_wait() {
let made = Arc::new(AtomicUsize::new(0));
let crew = Crew::spawn(seats(2, 4, 2), ToZero, |_| Spilling {
made: Arc::clone(&made),
each: 10,
})
.expect("the crew spawns");
crew.route(&(), ()).expect("the crew is alive");
thread::sleep(HELD);
assert!(
made.load(Ordering::SeqCst) <= 3,
"the worker ran past a full return line: {} made",
made.load(Ordering::SeqCst)
);
assert_eq!(crew.pending(), 2, "the line is not full");
let mut taken = crew.harvest().count();
let deadline = Instant::now() + PATIENCE;
while taken < 10 {
assert!(Instant::now() < deadline, "the worker never resumed");
taken += crew.harvest().count();
}
assert_eq!(made.load(Ordering::SeqCst), 10);
assert_eq!(crew.close().count(), 0, "everything was already harvested");
}
#[test]
fn a_full_return_line_does_not_wedge_a_full_in_queue() {
let made = Arc::new(AtomicUsize::new(0));
let crew = Crew::spawn(seats(2, 1, 2), ToZero, |_| Spilling {
made: Arc::clone(&made),
each: 8,
})
.expect("the crew spawns");
let routed = Arc::new(AtomicBool::new(false));
let hand = thread::spawn({
let routed = Arc::clone(&routed);
move || {
for _ in 0..6 {
crew.route(&(), ()).expect("the crew is alive");
}
routed.store(true, Ordering::SeqCst);
crew.close().count()
}
});
let deadline = Instant::now() + PATIENCE;
while !routed.load(Ordering::SeqCst) {
assert!(
Instant::now() < deadline,
"a full return line wedged a full in-queue"
);
thread::sleep(Duration::from_millis(5));
}
let tail = hand.join().expect("the routing thread");
assert_eq!(
made.load(Ordering::SeqCst),
48,
"six tasks of eight results"
);
assert!(tail <= 48);
}
struct Slow {
gone: Arc<AtomicUsize>,
}
impl Bench for Slow {
type Task = u64;
type Yield = u64;
fn work(&mut self, task: u64) -> impl IntoIterator<Item = u64> {
thread::sleep(Duration::from_millis(5));
[task]
}
}
impl Drop for Slow {
fn drop(&mut self) {
self.gone.fetch_add(1, Ordering::SeqCst);
}
}
#[test]
fn close_drains_the_tails_then_joins() {
let gone = Arc::new(AtomicUsize::new(0));
let crew = Crew::spawn(seats(2, 8, 64), HashRouter::new(), |_| Slow {
gone: Arc::clone(&gone),
})
.expect("the crew spawns");
for task in 0..8 {
crew.route(&task, task).expect("the crew is alive");
}
let mut tail: Vec<u64> = crew.close().collect();
tail.sort_unstable();
assert_eq!(tail, (0..8).collect::<Vec<_>>());
assert_eq!(gone.load(Ordering::SeqCst), 2, "a worker was not joined");
}
#[test]
fn dropping_without_closing_winds_the_crew_down() {
let gone = Arc::new(AtomicUsize::new(0));
let crew = Crew::spawn(seats(3, 8, 64), HashRouter::new(), |_| Slow {
gone: Arc::clone(&gone),
})
.expect("the crew spawns");
for task in 0..6 {
crew.route(&task, task).expect("the crew is alive");
}
drop(crew);
assert_eq!(
gone.load(Ordering::SeqCst),
3,
"the backstop returned before every worker was joined"
);
}
#[test]
fn a_drop_during_an_unwind_neither_deadlocks_nor_leaks_a_worker() {
let gone = Arc::new(AtomicUsize::new(0));
let made = Arc::new(AtomicUsize::new(0));
let finished = Arc::new(AtomicBool::new(false));
let dying = thread::spawn({
let (gone, made, finished) = (Arc::clone(&gone), Arc::clone(&made), Arc::clone(&finished));
move || {
let outcome = std::panic::catch_unwind(AssertUnwindSafe(|| {
let crew = Crew::spawn(seats(2, 4, 2), ToZero, |_| Unwound {
gone: Arc::clone(&gone),
made: Arc::clone(&made),
})
.expect("the crew spawns");
crew.route(&(), ()).expect("the crew is alive");
crew.route(&(), ()).expect("the crew is alive");
panic!("the body dies inside its own loop");
}));
assert!(outcome.is_err(), "the panic was swallowed");
finished.store(true, Ordering::SeqCst);
}
});
let deadline = Instant::now() + PATIENCE;
while !finished.load(Ordering::SeqCst) {
assert!(
Instant::now() < deadline,
"the drop backstop deadlocked on the unwind path"
);
thread::sleep(Duration::from_millis(5));
}
dying.join().expect("the dying thread");
assert_eq!(
gone.load(Ordering::SeqCst),
2,
"a worker was left behind by the unwind"
);
}
struct Unwound {
gone: Arc<AtomicUsize>,
made: Arc<AtomicUsize>,
}
impl Bench for Unwound {
type Task = ();
type Yield = usize;
fn work(&mut self, (): ()) -> impl IntoIterator<Item = usize> {
Spill {
made: Arc::clone(&self.made),
left: 32,
}
}
}
impl Drop for Unwound {
fn drop(&mut self) {
self.gone.fetch_add(1, Ordering::SeqCst);
}
}
#[test]
fn a_hash_router_answers_the_same_key_the_same_way() {
let router = HashRouter::new();
let first = router.route("track/7");
assert_eq!(first, router.route("track/7"));
assert_eq!(first, router.route("track/7"), "and again");
#[derive(Clone, Default)]
struct Zeroed;
impl core::hash::BuildHasher for Zeroed {
type Hasher = std::collections::hash_map::DefaultHasher;
fn build_hasher(&self) -> Self::Hasher {
Self::Hasher::default()
}
}
assert_eq!(
HashRouter::with_hasher(Zeroed).route("track/7"),
HashRouter::with_hasher(Zeroed).route("track/7"),
"a fixed hasher is what makes two routers agree"
);
}
#[test]
fn the_seats_ship_their_defaults() {
let seats = CrewOptions::new();
assert_eq!(seats, CrewOptions::default());
assert_eq!(seats.workers(), super::DEFAULT_WORKERS);
assert_eq!(seats.queue_depth(), super::DEFAULT_QUEUE_DEPTH);
assert_eq!(seats.return_depth(), super::DEFAULT_RETURN_DEPTH);
assert_eq!(seats.label(), DEFAULT_LABEL);
assert_eq!(seats.workers().get(), 1);
let tuned = seats
.with_workers(NonZeroUsize::new(4).expect("not zero"))
.with_queue_depth(NonZeroUsize::new(2).expect("not zero"))
.with_return_depth(NonZeroUsize::new(8).expect("not zero"))
.with_label("resample");
assert_eq!(tuned.workers().get(), 4);
assert_eq!(tuned.queue_depth().get(), 2);
assert_eq!(tuned.return_depth().get(), 8);
assert_eq!(tuned.label(), "resample");
let mut in_place = CrewOptions::new();
in_place
.set_workers(NonZeroUsize::new(4).expect("not zero"))
.set_queue_depth(NonZeroUsize::new(2).expect("not zero"))
.set_return_depth(NonZeroUsize::new(8).expect("not zero"))
.set_label("resample");
assert_eq!(in_place, tuned, "the two spellings say the same thing");
}
struct Twinning {
taking: Duration,
started: conduit::Sender<()>,
}
impl Bench for Twinning {
type Task = u64;
type Yield = u64;
fn work(&mut self, task: u64) -> impl IntoIterator<Item = u64> {
drop(self.started.try_send(()));
thread::sleep(self.taking);
[task * 2, task * 2 + 1]
}
}
#[test]
fn a_pinned_arm_over_a_waiting_route_still_hands_one_bench_its_own_order() {
use core::pin::pin;
for attempt in 0..6 {
let (started, starts) = conduit::bounded::<()>(8);
let crew = Crew::spawn(seats(2, 1, 64), ToZero, |_| Twinning {
taking: Duration::from_millis(25),
started: started.clone(),
})
.expect("the crew spawns");
drop(started);
{
let mut worked = pin!(crew.returns().arm(true, || ()));
assert!(
park_on(worked.as_mut(), Duration::from_millis(5)).is_none(),
"attempt {attempt}: the crew spoke before it had been given anything"
);
crew.route(&(), 0).expect("the crew is alive");
assert!(
park_on(starts.recv_async(), PATIENCE).is_some(),
"attempt {attempt}: the bench never started"
);
crew.route(&(), 1).expect("the crew is alive");
crew.route(&(), 2).expect("the crew is alive");
}
let mut got: Vec<u64> = crew.harvest().collect();
got.extend(crew.close());
assert_eq!(
got,
vec![0, 1, 2, 3, 4, 5],
"attempt {attempt}: one bench's results came back out of the order it made them in"
);
}
}
#[test]
fn one_key_keeps_its_order_through_an_armed_loop_under_contention() {
use core::pin::pin;
use crate::conduit::{Arm, select};
enum Turn {
Fed((u64, u64)),
Worked,
}
struct Fanning;
impl Bench for Fanning {
type Task = (u64, u64);
type Yield = (u64, u64);
fn work(&mut self, (key, seq): (u64, u64)) -> impl IntoIterator<Item = (u64, u64)> {
(0..3).map(move |step| (key, seq * 3 + step))
}
}
fn drive() -> BTreeMap<u64, Vec<u64>> {
let crew =
Crew::spawn(seats(4, 2, 4), HashRouter::new(), |_| Fanning).expect("the crew spawns");
let (feed, from_feed) = conduit::bounded::<(u64, u64)>(256);
for seq in 0..8 {
for key in 0..4 {
feed.send((key, seq)).expect("the feed holds it");
}
}
drop(feed);
let mut out: Vec<(u64, u64)> = Vec::new();
let mut turn = 0usize;
let mut feeding = true;
loop {
{
let mut fed = pin!(conduit::arm(feeding, &from_feed, Turn::Fed));
let mut worked = pin!(crew.returns().arm(true, || Turn::Worked));
let mut arms: [Arm<'_, Option<Turn>>; 2] = [fed.as_mut(), worked.as_mut()];
match park_on(select(turn, &mut arms), Duration::from_millis(20)) {
None | Some(None) => {}
Some(Some((index, heard))) => {
turn = index + 1;
match heard {
None => feeding = false,
Some(Turn::Fed((key, seq))) => {
crew.route(&key, (key, seq)).expect("the crew is alive");
}
Some(Turn::Worked) => {}
}
}
}
}
out.extend(crew.harvest());
if !feeding {
break;
}
}
out.extend(crew.close());
let mut grouped: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
for (key, seq) in out {
grouped.entry(key).or_default().push(seq);
}
grouped
}
let stop = Arc::new(AtomicBool::new(false));
let burners: Vec<_> = (0..8)
.map(|_| {
let stop = Arc::clone(&stop);
thread::spawn(move || {
let mut spun = 0u64;
while !stop.load(Ordering::Relaxed) {
spun = spun.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
std::hint::black_box(spun);
}
})
})
.collect();
let want: Vec<u64> = (0..24).collect();
let mut broke = 0usize;
let mut first: Vec<(usize, u64, Vec<u64>)> = Vec::new();
for round in 0..120 {
for (key, seq) in drive() {
if seq != want {
broke += 1;
if first.len() < 3 {
first.push((round, key, seq));
}
}
}
}
stop.store(true, Ordering::Relaxed);
for burner in burners {
burner.join().expect("the burner ends");
}
assert_eq!(
broke, 0,
"a key's own sequence interleaved with itself, {broke} times — first: {first:?}"
);
}