use super::*;
use std::sync::atomic::{AtomicBool, AtomicUsize};
use std::sync::{Arc, mpsc};
use std::time::{Duration, Instant};
type TestHook = Box<dyn FnOnce()>;
thread_local! {
static AFTER_EMPTY_SHARD: Cell<Option<TestHook>> = const { Cell::new(None) };
static AFTER_SHARD_CLOSED: Cell<Option<TestHook>> = const { Cell::new(None) };
}
pub(super) fn after_empty_shard_scan() {
AFTER_EMPTY_SHARD.with(|hook| {
if let Some(hook) = hook.take() {
hook();
}
});
}
pub(super) fn after_shard_closed() {
AFTER_SHARD_CLOSED.with(|hook| {
if let Some(hook) = hook.take() {
hook();
}
});
}
#[test]
fn empty_scan_is_not_a_global_snapshot() {
let s = Arc::new(ConcurrentShardedStack::with_concurrency(2));
THREAD_ID.with(|id| id.set(1));
s.push("original").unwrap();
let (scanned_tx, scanned_rx) = mpsc::channel();
let (resume_tx, resume_rx) = mpsc::channel();
let stack = Arc::clone(&s);
let popper = thread::spawn(move || {
THREAD_ID.with(|id| id.set(0));
AFTER_EMPTY_SHARD.with(|hook| {
hook.set(Some(Box::new(move || {
scanned_tx.send(()).unwrap();
resume_rx.recv().unwrap();
})));
});
stack.pop()
});
scanned_rx.recv_timeout(Duration::from_secs(30)).unwrap();
THREAD_ID.with(|id| id.set(0));
s.push("replacement").unwrap();
THREAD_ID.with(|id| id.set(1));
assert_eq!(s.pop(), Ok("original"));
resume_tx.send(()).unwrap();
assert_eq!(popper.join().unwrap(), Err(PopError::Empty));
assert_eq!(s.pop(), Ok("replacement"));
}
#[test]
fn close_propagates_per_shard_and_can_have_multiple_winners() {
let s = Arc::new(ConcurrentShardedStack::with_concurrency(2));
let (closed_tx, closed_rx) = mpsc::channel();
let (resume_tx, resume_rx) = mpsc::channel();
let stack = Arc::clone(&s);
let closer = thread::spawn(move || {
AFTER_SHARD_CLOSED.with(|hook| {
hook.set(Some(Box::new(move || {
closed_tx.send(()).unwrap();
resume_rx.recv().unwrap();
})));
});
stack.close()
});
closed_rx.recv_timeout(Duration::from_secs(30)).unwrap();
THREAD_ID.with(|id| id.set(0));
assert_eq!(s.push(1), Err(PushError::Closed(1)));
assert!(!s.is_closed());
THREAD_ID.with(|id| id.set(1));
assert_eq!(s.push(2), Ok(()));
assert!(s.close());
assert!(s.is_closed());
resume_tx.send(()).unwrap();
assert!(closer.join().unwrap());
assert_eq!(s.pop(), Ok(2));
assert_eq!(s.pop(), Err(PopError::Closed));
}
#[test]
fn payload_panic_still_drops_remaining_nodes_and_shards() {
use std::panic::{AssertUnwindSafe, catch_unwind};
struct Payload {
panic: bool,
drops: Arc<AtomicUsize>,
}
impl Drop for Payload {
fn drop(&mut self) {
self.drops.fetch_add(1, Ordering::Relaxed);
assert!(!self.panic, "payload destructor panic");
}
}
for first_shard in [0, 2] {
let drops = Arc::new(AtomicUsize::new(0));
let s = ConcurrentShardedStack::with_concurrency(4);
for (shard, panic) in [(first_shard, false), (first_shard, true), (3, false)] {
THREAD_ID.with(|id| id.set(shard));
assert!(
s.push(Payload {
panic,
drops: Arc::clone(&drops)
})
.is_ok()
);
}
assert!(catch_unwind(AssertUnwindSafe(|| drop(s))).is_err());
assert_eq!(drops.load(Ordering::Relaxed), 3);
}
}
#[derive(Debug)]
struct DropCounter {
counter: Arc<AtomicUsize>,
}
impl DropCounter {
fn new(counter: Arc<AtomicUsize>) -> Self {
Self { counter }
}
}
impl Drop for DropCounter {
fn drop(&mut self) {
self.counter.fetch_add(1, Ordering::Relaxed);
}
}
#[test]
fn new_requires_power_of_two() {
let s = ConcurrentShardedStack::<usize>::with_concurrency(4);
assert_eq!(s.shard_count(), 4);
}
#[test]
#[should_panic]
fn new_panics_if_not_power_of_two() {
let _ = ConcurrentShardedStack::<usize>::with_concurrency(3);
}
#[test]
fn push_pop_single_thread() {
let s = ConcurrentShardedStack::with_concurrency(4);
s.push(1).unwrap();
s.push(2).unwrap();
s.push(3).unwrap();
assert_eq!(s.pop().unwrap(), 3);
assert_eq!(s.pop().unwrap(), 2);
assert_eq!(s.pop().unwrap(), 1);
assert_eq!(s.pop(), Err(PopError::Empty));
}
#[test]
fn close_works() {
let s = ConcurrentShardedStack::with_concurrency(4);
assert!(s.push(1).is_ok());
assert!(s.close());
assert!(!s.close());
assert_eq!(s.push(2), Err(PushError::Closed(2)));
assert_eq!(s.pop().unwrap(), 1);
assert_eq!(s.pop(), Err(PopError::Closed));
}
#[test]
fn multi_thread_push_pop() {
let s = Arc::new(ConcurrentShardedStack::with_concurrency(8));
let threads = 8;
#[cfg(miri)]
let per_thread = 200;
#[cfg(not(miri))]
let per_thread = 10_000;
let mut handles = Vec::new();
for t in 0..threads {
let s = Arc::clone(&s);
handles.push(std::thread::spawn(move || {
for i in 0..per_thread {
s.push(t * per_thread + i).unwrap();
}
}));
}
for handle in handles {
handle.join().unwrap();
}
let mut handles = Vec::new();
for _ in 0..threads {
let s = Arc::clone(&s);
handles.push(std::thread::spawn(move || {
let mut count = 0usize;
loop {
match s.pop() {
Ok(_) => count += 1,
Err(PopError::Empty) => break,
Err(PopError::Closed) => break,
}
}
count
}));
}
let total: usize = handles.into_iter().map(|h| h.join().unwrap()).sum();
assert_eq!(total, threads * per_thread);
}
#[test]
fn close_after_drain_returns_closed() {
let s = ConcurrentShardedStack::with_concurrency(4);
for i in 0..100 {
s.push(i).unwrap();
}
assert!(s.close());
let mut count = 0;
loop {
match s.pop() {
Ok(_) => count += 1,
Err(PopError::Empty) => continue,
Err(PopError::Closed) => break,
}
}
assert_eq!(count, 100);
}
#[test]
fn popped_values_are_dropped_exactly_once() {
let counter = Arc::new(AtomicUsize::new(0));
let s = ConcurrentShardedStack::with_concurrency(4);
for _ in 0..50 {
s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
}
let mut popped = 0;
while let Ok(value) = s.pop() {
drop(value);
popped += 1;
}
assert_eq!(popped, 50);
drop(s);
epoch::pin().flush();
assert_eq!(counter.load(Ordering::Relaxed), 50);
}
#[test]
fn remaining_values_are_dropped_when_stack_is_dropped() {
let counter = Arc::new(AtomicUsize::new(0));
{
let s = ConcurrentShardedStack::with_concurrency(4);
for _ in 0..30 {
s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
}
}
assert_eq!(counter.load(Ordering::Relaxed), 30);
}
#[test]
fn partially_drained_stack_drops_each_value_once() {
let counter = Arc::new(AtomicUsize::new(0));
{
let s = ConcurrentShardedStack::with_concurrency(4);
for _ in 0..40 {
s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
}
for _ in 0..15 {
let _ = s.pop().unwrap();
}
}
epoch::pin().flush();
assert_eq!(counter.load(Ordering::Relaxed), 40);
}
#[test]
fn concurrent_drop_counter_no_double_free() {
let counter = Arc::new(AtomicUsize::new(0));
let s = Arc::new(ConcurrentShardedStack::with_concurrency(4));
let threads = 4;
#[cfg(miri)]
let per_thread = 50;
#[cfg(not(miri))]
let per_thread = 200;
let mut handles = Vec::new();
for _ in 0..threads {
let s = Arc::clone(&s);
let counter = Arc::clone(&counter);
handles.push(std::thread::spawn(move || {
for _ in 0..per_thread {
s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
}
}));
}
for h in handles {
h.join().unwrap();
}
let mut handles = Vec::new();
for _ in 0..threads {
let s = Arc::clone(&s);
handles.push(std::thread::spawn(move || {
let mut popped = 0;
while let Ok(value) = s.pop() {
drop(value);
popped += 1;
}
popped
}));
}
let total: usize = handles.into_iter().map(|h| h.join().unwrap()).sum();
assert_eq!(total, threads * per_thread);
drop(s);
epoch::pin().flush();
assert_eq!(counter.load(Ordering::Relaxed), threads * per_thread);
}
fn wait_until<F: Fn() -> bool>(timeout: Duration, label: &str, cond: F) {
let start = Instant::now();
while !cond() {
if start.elapsed() > timeout {
panic!("{label}: condition not met within {timeout:?}");
}
std::thread::sleep(Duration::from_millis(5));
}
}
#[cfg_attr(miri, ignore)]
#[test]
fn no_element_loss_open_asymmetric() {
#[cfg(miri)]
let (n_pushers, n_poppers, per_pusher, rounds) = (2, 2, 200, 1);
#[cfg(not(miri))]
let (n_pushers, n_poppers, per_pusher, rounds) = (4, 12, 50_000, 4);
for round in 0..rounds {
let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(16));
let popped = Arc::new(AtomicUsize::new(0));
let pushed = Arc::new(AtomicUsize::new(0));
let stop = Arc::new(AtomicBool::new(false));
let total = n_pushers * per_pusher;
let mut handles = Vec::new();
for t in 0..n_pushers {
let s = Arc::clone(&s);
let pushed = Arc::clone(&pushed);
handles.push(std::thread::spawn(move || {
for i in 0..per_pusher {
s.push(t * per_pusher + i).unwrap();
pushed.fetch_add(1, Ordering::Relaxed);
}
}));
}
for _ in 0..n_poppers {
let s = Arc::clone(&s);
let popped = Arc::clone(&popped);
let stop = Arc::clone(&stop);
handles.push(std::thread::spawn(move || {
while !stop.load(Ordering::Relaxed) {
match s.pop() {
Ok(_) => {
popped.fetch_add(1, Ordering::Relaxed);
}
Err(PopError::Empty) => std::hint::spin_loop(),
Err(PopError::Closed) => break,
}
}
}));
}
wait_until(Duration::from_secs(30), "popper drain (open)", || {
popped.load(Ordering::Relaxed) >= total
});
stop.store(true, Ordering::Relaxed);
for h in handles {
h.join().unwrap();
}
let final_pushed = pushed.load(Ordering::Relaxed);
let final_popped = popped.load(Ordering::Relaxed);
assert_eq!(
final_popped, final_pushed,
"round {round}: popped {final_popped} != pushed {final_pushed}",
);
}
}
#[test]
fn no_element_loss_after_close_asymmetric() {
#[cfg(miri)]
let (n_pushers, n_poppers, per_pusher, rounds) = (2, 2, 200, 1);
#[cfg(not(miri))]
let (n_pushers, n_poppers, per_pusher, rounds) = (4, 12, 50_000, 4);
for round in 0..rounds {
let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(16));
let popped = Arc::new(AtomicUsize::new(0));
let total = n_pushers * per_pusher;
let mut handles = Vec::new();
for t in 0..n_pushers {
let s = Arc::clone(&s);
handles.push(std::thread::spawn(move || {
for i in 0..per_pusher {
s.push(t * per_pusher + i).unwrap();
}
}));
}
for _ in 0..n_poppers {
let s = Arc::clone(&s);
let popped = Arc::clone(&popped);
handles.push(std::thread::spawn(move || {
loop {
match s.pop() {
Ok(_) => {
popped.fetch_add(1, Ordering::Relaxed);
}
Err(PopError::Empty) => std::hint::spin_loop(),
Err(PopError::Closed) => break,
}
}
}));
}
let pusher_handles: Vec<_> = handles.drain(..n_pushers).collect();
for h in pusher_handles {
h.join().unwrap();
}
s.close();
for h in handles {
h.join().unwrap();
}
assert_eq!(
popped.load(Ordering::Relaxed),
total,
"round {round}: drain after close lost elements",
);
}
}
#[test]
fn no_element_loss_few_threads_many_shards() {
#[cfg(miri)]
let (n_pushers, n_poppers, per_pusher, shards) = (2, 1, 100, 8);
#[cfg(not(miri))]
let (n_pushers, n_poppers, per_pusher, shards) = (2, 1, 100_000, 32);
let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(shards));
let popped = Arc::new(AtomicUsize::new(0));
let total = n_pushers * per_pusher;
let mut handles = Vec::new();
for _ in 0..n_pushers {
let s = Arc::clone(&s);
handles.push(std::thread::spawn(move || {
for i in 0..per_pusher {
s.push(i).unwrap();
}
}));
}
for _ in 0..n_poppers {
let s = Arc::clone(&s);
let popped = Arc::clone(&popped);
handles.push(std::thread::spawn(move || {
let start = Instant::now();
while popped.load(Ordering::Relaxed) < total {
match s.pop() {
Ok(_) => {
popped.fetch_add(1, Ordering::Relaxed);
}
Err(PopError::Empty) => std::hint::spin_loop(),
Err(PopError::Closed) => break,
}
if start.elapsed() > Duration::from_secs(30) {
panic!(
"popper stuck: popped {} of {}",
popped.load(Ordering::Relaxed),
total,
);
}
}
}));
}
for h in handles {
h.join().unwrap();
}
assert_eq!(popped.load(Ordering::Relaxed), total);
}