Skip to main content

concurrent_sharded_stack/
lib.rs

1//! A lock-free concurrent stack that shards a classic Treiber stack across
2//! multiple per-thread shards and reclaims memory with epoch-based GC.
3//!
4//! See [`ConcurrentShardedStack`] for the main entry point. Compared to a
5//! single Treiber stack, sharding spreads CAS contention across independent
6//! cache-line-padded shards, at the cost of only providing LIFO ordering
7//! *within* a shard rather than globally.
8//!
9//! # Example
10//!
11//! ```
12//! use concurrent_sharded_stack::{ConcurrentShardedStack, PopError};
13//!
14//! let stack = ConcurrentShardedStack::with_concurrency(4);
15//! stack.push(1).unwrap();
16//! stack.push(2).unwrap();
17//!
18//! assert_eq!(stack.pop().unwrap(), 2);
19//! assert_eq!(stack.pop().unwrap(), 1);
20//! assert_eq!(stack.pop(), Err(PopError::Empty));
21//! ```
22
23use crossbeam_epoch::{self as epoch, Atomic, Guard, Owned};
24use crossbeam_utils::CachePadded;
25use std::cell::Cell;
26use std::fmt;
27use std::hint::spin_loop;
28use std::mem::ManuallyDrop;
29use std::ptr;
30use std::sync::atomic::{AtomicUsize, Ordering};
31use std::thread;
32
33static NEXT_THREAD_ID: AtomicUsize = AtomicUsize::new(0);
34
35const CLOSED_TAG: usize = 1;
36
37thread_local! {
38    static THREAD_ID: Cell<usize> = Cell::new(
39        NEXT_THREAD_ID.fetch_add(1, Ordering::Relaxed)
40    );
41}
42
43fn current_thread_id() -> usize {
44    THREAD_ID.with(Cell::get)
45}
46
47#[derive(Debug, PartialEq, Eq)]
48pub enum PushError<T> {
49    /// The target shard has been closed.
50    Closed(T),
51}
52
53impl<T> PushError<T> {
54    pub fn into_inner(self) -> T {
55        match self {
56            PushError::Closed(v) => v,
57        }
58    }
59}
60
61impl<T> fmt::Display for PushError<T> {
62    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
63        match self {
64            PushError::Closed(_) => write!(f, "stack is closed"),
65        }
66    }
67}
68
69impl<T: fmt::Debug> std::error::Error for PushError<T> {}
70
71#[derive(Debug, Clone, Copy, PartialEq, Eq)]
72pub enum PopError {
73    /// No item was found by this scan; concurrent activity may hide items.
74    Empty,
75    /// Every shard was observed closed and empty; no later push can succeed.
76    Closed,
77}
78
79impl fmt::Display for PopError {
80    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
81        match self {
82            PopError::Empty => write!(f, "stack is empty"),
83            PopError::Closed => write!(f, "stack is closed"),
84        }
85    }
86}
87
88impl std::error::Error for PopError {}
89
90struct Node<T> {
91    value: ManuallyDrop<T>,
92    next: Atomic<Node<T>>,
93}
94
95impl<T> Node<T> {
96    fn new(value: T) -> Self {
97        Self {
98            value: ManuallyDrop::new(value),
99            next: Atomic::null(),
100        }
101    }
102}
103
104enum ShardPopResult<T> {
105    Popped(T),
106    Empty,
107    EmptyAndClosed,
108}
109
110/// Concurrent sharded Treiber stack.
111///
112/// Ordering is LIFO within each shard, not across shards. An unsuccessful
113/// [`pop`](Self::pop) is a scan, not an atomic snapshot: `Empty` can be returned
114/// even when the stack remained nonempty throughout the call. Closing also
115/// takes effect one shard at a time; see [`close`](Self::close).
116pub struct ConcurrentShardedStack<T> {
117    shards: Box<[CachePadded<Atomic<Node<T>>>]>,
118    shard_index_mask: usize,
119}
120
121unsafe impl<T: Send> Send for ConcurrentShardedStack<T> {}
122unsafe impl<T: Send> Sync for ConcurrentShardedStack<T> {}
123
124impl<T> Default for ConcurrentShardedStack<T> {
125    fn default() -> Self {
126        Self::new()
127    }
128}
129
130impl<T> ConcurrentShardedStack<T> {
131    /// Creates a stack using `available_parallelism()` as concurrency hint.
132    pub fn new() -> Self {
133        let concurrency = thread::available_parallelism()
134            .map(|n| n.get().next_power_of_two())
135            .unwrap_or(4);
136
137        Self::with_concurrency(concurrency)
138    }
139
140    /// Creates a stack with exact shard count.
141    ///
142    /// Panics if:
143    ///
144    /// - `shard_count == 0`
145    /// - `shard_count` is not power of two
146    pub fn with_concurrency(shard_count: usize) -> Self {
147        assert!(shard_count > 0, "shard_count must be non-zero");
148
149        assert!(
150            shard_count.is_power_of_two(),
151            "shard_count must be a power of two"
152        );
153
154        let mut shards = Vec::with_capacity(shard_count);
155
156        for _ in 0..shard_count {
157            shards.push(CachePadded::new(Atomic::null()));
158        }
159
160        Self {
161            shards: shards.into_boxed_slice(),
162            shard_index_mask: shard_count - 1,
163        }
164    }
165
166    /// Pushes a value into the stack.
167    ///
168    /// Returns `Err(PushError::Closed(value))` if this thread's shard is closed.
169    /// While [`close`](Self::close) is in progress, some shards may reject
170    /// pushes while others still accept them. After `close` returns, every
171    /// shard rejects pushes.
172    pub fn push(&self, value: T) -> Result<(), PushError<T>> {
173        let shard_index = self.current_shard_index();
174        let shard = &self.shards[shard_index];
175
176        let guard = &epoch::pin();
177        let mut node = Owned::new(Node::new(value));
178
179        loop {
180            let head = shard.load(Ordering::Acquire, guard);
181
182            if head.tag() == CLOSED_TAG {
183                let node = node.into_box();
184                let value = unsafe { ptr::read(&*node.value) };
185                return Err(PushError::Closed(value));
186            }
187
188            node.next.store(head, Ordering::Relaxed);
189
190            match shard.compare_exchange_weak(
191                head,
192                node,
193                Ordering::Release,
194                Ordering::Relaxed,
195                guard,
196            ) {
197                Ok(_) => return Ok(()),
198                Err(err) => {
199                    node = err.new;
200                    spin_loop();
201                }
202            }
203        }
204    }
205
206    /// Pops a value from the stack non-blocking.
207    ///
208    /// Scan order:
209    ///
210    /// - first scan the current thread's own shard;
211    /// - then scan the shard whose last binary bit differs;
212    /// - then scan shards whose next binary bit differs;
213    /// - continue widening the differing-bit window until all shards are scanned.
214    ///
215    /// For example, with 8 shards and local shard `start`, the XOR masks are:
216    ///
217    /// ```text
218    /// 0,
219    /// 1,
220    /// 2, 3,
221    /// 4, 5, 6, 7
222    /// ```
223    ///
224    /// So the actual scan order is:
225    ///
226    /// ```text
227    /// start,
228    /// start ^ 1,
229    /// start ^ 2, start ^ 3,
230    /// start ^ 4, start ^ 5, start ^ 6, start ^ 7
231    /// ```
232    ///
233    /// Returns `Err(PopError::Empty)` if no element is found and at least one
234    /// shard is still observed open. This is not a consistent snapshot: other
235    /// threads can push into an already-scanned shard and drain a later shard,
236    /// so `Empty` can occur even if the stack was never globally empty during
237    /// the call. Consumers with active producers should retry rather than use
238    /// `Empty` as a completion signal.
239    ///
240    /// Returns `Err(PopError::Closed)` if no element is found and every shard
241    /// is observed closed. Unlike `Empty`, this is terminal: closed shards
242    /// cannot receive more elements.
243    pub fn pop(&self) -> Result<T, PopError> {
244        let guard = &epoch::pin();
245        let start = self.current_shard_index();
246        let shard_count = self.shards.len();
247
248        let mut all_closed = true;
249
250        for mask in 0..shard_count {
251            let index = start ^ mask;
252
253            match self.pop_one(index, guard) {
254                ShardPopResult::Popped(value) => return Ok(value),
255                ShardPopResult::Empty => {
256                    all_closed = false;
257                }
258                ShardPopResult::EmptyAndClosed => {}
259            }
260            #[cfg(test)]
261            tests::after_empty_shard_scan();
262        }
263
264        if all_closed {
265            Err(PopError::Closed)
266        } else {
267            Err(PopError::Empty)
268        }
269    }
270
271    /// Closes every shard. Existing elements can still be popped.
272    ///
273    /// Closure propagates one shard at a time. During the call, a push can be
274    /// rejected on one shard while a later push succeeds on another, and
275    /// [`is_closed`](Self::is_closed) can still return `false` after a rejected
276    /// push. Once this method returns, all shards are closed.
277    ///
278    /// Returns `true` if this call closed at least one shard. Concurrent calls
279    /// can both return `true`; the result does not identify a unique closer.
280    pub fn close(&self) -> bool {
281        let guard = &epoch::pin();
282        let mut changed = false;
283
284        for shard in self.shards.iter() {
285            loop {
286                let head = shard.load(Ordering::Acquire, guard);
287
288                if head.tag() == CLOSED_TAG {
289                    break;
290                }
291
292                match shard.compare_exchange_weak(
293                    head,
294                    head.with_tag(CLOSED_TAG),
295                    Ordering::AcqRel,
296                    Ordering::Relaxed,
297                    guard,
298                ) {
299                    Ok(_) => {
300                        changed = true;
301                        #[cfg(test)]
302                        tests::after_shard_closed();
303                        break;
304                    }
305                    Err(_) => spin_loop(),
306                }
307            }
308        }
309
310        changed
311    }
312
313    /// Checks whether every shard is closed.
314    pub fn is_closed(&self) -> bool {
315        let guard = &epoch::pin();
316        self.all_shards_closed(guard)
317    }
318
319    pub fn shard_count(&self) -> usize {
320        self.shards.len()
321    }
322
323    fn current_shard_index(&self) -> usize {
324        current_thread_id() & self.shard_index_mask
325    }
326
327    /// Pops from one shard.
328    ///
329    /// This function loops until the shard produces a definite result:
330    ///
331    /// - popped one value;
332    /// - or the shard is observed empty.
333    ///
334    /// CAS failures are retried indefinitely for this shard. There is no fixed
335    /// retry budget anymore.
336    ///
337    /// Returns:
338    ///
339    /// - `value: Some(T)` if a value was popped;
340    /// - `value: None` if this shard is currently empty;
341    /// - `closed` indicates whether this shard was observed closed.
342    fn pop_one(&self, index: usize, guard: &Guard) -> ShardPopResult<T> {
343        let shard = &self.shards[index];
344
345        loop {
346            let head = shard.load(Ordering::Acquire, guard);
347            let closed = head.tag() == CLOSED_TAG;
348
349            if head.is_null() {
350                return if closed {
351                    ShardPopResult::EmptyAndClosed
352                } else {
353                    ShardPopResult::Empty
354                };
355            }
356
357            let head_ref = unsafe { head.deref() };
358
359            // `head` was published by a Release CAS that we synchronized with
360            // via the Acquire load above, so the node's fields are visible.
361            let next = head_ref.next.load(Ordering::Relaxed, guard);
362
363            // Preserve the CLOSED tag when popping from a closed shard.
364            let new_head = next.with_tag(head.tag());
365
366            match shard.compare_exchange(head, new_head, Ordering::AcqRel, Ordering::Relaxed, guard)
367            {
368                Ok(_) => {
369                    // Move the value out of the popped node. The node itself
370                    // is reclaimed later by epoch GC; because `value` is inside
371                    // `ManuallyDrop<T>`, deferred destruction will not drop it again.
372                    let value = unsafe { ptr::read(&*head_ref.value) };
373
374                    unsafe {
375                        guard.defer_destroy(head.with_tag(0));
376                    }
377
378                    return ShardPopResult::Popped(value);
379                }
380                Err(_) => {
381                    spin_loop();
382                }
383            }
384        }
385    }
386
387    fn all_shards_closed(&self, guard: &Guard) -> bool {
388        self.shards
389            .iter()
390            .all(|shard| shard.load(Ordering::Acquire, guard).tag() == CLOSED_TAG)
391    }
392}
393
394impl<T> Drop for ConcurrentShardedStack<T> {
395    fn drop(&mut self) {
396        let guard = &epoch::pin();
397        let drain = || {
398            for shard in &self.shards {
399                loop {
400                    let current = shard.load(Ordering::Relaxed, guard);
401                    if current.is_null() {
402                        break;
403                    }
404
405                    // SAFETY: dropping the stack requires exclusive access,
406                    // so no operation can still access its reachable nodes.
407                    // Advance the head before user code so a panic leaves only
408                    // the remaining nodes reachable for the cleanup guard.
409                    unsafe {
410                        let mut node = Box::from_raw(current.as_raw() as *mut Node<T>);
411                        let next = node.next.load(Ordering::Relaxed, guard);
412                        shard.store(next, Ordering::Relaxed);
413                        ManuallyDrop::drop(&mut node.value);
414                    }
415                }
416            }
417        };
418
419        let cleanup = scopeguard::guard((), |_| drain());
420        drain();
421        scopeguard::ScopeGuard::into_inner(cleanup);
422    }
423}
424
425#[cfg(test)]
426mod tests {
427    use super::*;
428    use std::sync::atomic::{AtomicBool, AtomicUsize};
429    use std::sync::{Arc, mpsc};
430    use std::time::{Duration, Instant};
431
432    // One-shot, per-thread hooks expose deterministic interleavings without
433    // adding any instructions to non-test builds.
434    type TestHook = Box<dyn FnOnce()>;
435    thread_local! {
436        static AFTER_EMPTY_SHARD: Cell<Option<TestHook>> = const { Cell::new(None) };
437        static AFTER_SHARD_CLOSED: Cell<Option<TestHook>> = const { Cell::new(None) };
438    }
439
440    pub(super) fn after_empty_shard_scan() {
441        AFTER_EMPTY_SHARD.with(|hook| {
442            if let Some(hook) = hook.take() {
443                hook();
444            }
445        });
446    }
447
448    pub(super) fn after_shard_closed() {
449        AFTER_SHARD_CLOSED.with(|hook| {
450            if let Some(hook) = hook.take() {
451                hook();
452            }
453        });
454    }
455
456    #[test]
457    fn empty_scan_is_not_a_global_snapshot() {
458        let s = Arc::new(ConcurrentShardedStack::with_concurrency(2));
459        THREAD_ID.with(|id| id.set(1));
460        s.push("original").unwrap();
461
462        let (scanned_tx, scanned_rx) = mpsc::channel();
463        let (resume_tx, resume_rx) = mpsc::channel();
464        let stack = Arc::clone(&s);
465        let popper = thread::spawn(move || {
466            THREAD_ID.with(|id| id.set(0));
467            AFTER_EMPTY_SHARD.with(|hook| {
468                hook.set(Some(Box::new(move || {
469                    scanned_tx.send(()).unwrap();
470                    resume_rx.recv().unwrap();
471                })));
472            });
473            stack.pop()
474        });
475
476        scanned_rx.recv_timeout(Duration::from_secs(30)).unwrap();
477        THREAD_ID.with(|id| id.set(0));
478        s.push("replacement").unwrap();
479        THREAD_ID.with(|id| id.set(1));
480        assert_eq!(s.pop(), Ok("original"));
481        // At least one item has existed throughout the pending pop.
482        resume_tx.send(()).unwrap();
483        assert_eq!(popper.join().unwrap(), Err(PopError::Empty));
484        assert_eq!(s.pop(), Ok("replacement"));
485    }
486
487    #[test]
488    fn close_propagates_per_shard_and_can_have_multiple_winners() {
489        let s = Arc::new(ConcurrentShardedStack::with_concurrency(2));
490        let (closed_tx, closed_rx) = mpsc::channel();
491        let (resume_tx, resume_rx) = mpsc::channel();
492        let stack = Arc::clone(&s);
493        let closer = thread::spawn(move || {
494            AFTER_SHARD_CLOSED.with(|hook| {
495                hook.set(Some(Box::new(move || {
496                    closed_tx.send(()).unwrap();
497                    resume_rx.recv().unwrap();
498                })));
499            });
500            stack.close()
501        });
502
503        closed_rx.recv_timeout(Duration::from_secs(30)).unwrap();
504        THREAD_ID.with(|id| id.set(0));
505        assert_eq!(s.push(1), Err(PushError::Closed(1)));
506        assert!(!s.is_closed());
507        THREAD_ID.with(|id| id.set(1));
508        assert_eq!(s.push(2), Ok(()));
509        assert!(s.close());
510        assert!(s.is_closed());
511        resume_tx.send(()).unwrap();
512        assert!(closer.join().unwrap());
513        assert_eq!(s.pop(), Ok(2));
514        assert_eq!(s.pop(), Err(PopError::Closed));
515    }
516
517    #[test]
518    fn payload_panic_still_drops_remaining_nodes_and_shards() {
519        use std::panic::{AssertUnwindSafe, catch_unwind};
520
521        struct Payload {
522            panic: bool,
523            drops: Arc<AtomicUsize>,
524        }
525        impl Drop for Payload {
526            fn drop(&mut self) {
527                self.drops.fetch_add(1, Ordering::Relaxed);
528                assert!(!self.panic, "payload destructor panic");
529            }
530        }
531
532        for first_shard in [0, 2] {
533            let drops = Arc::new(AtomicUsize::new(0));
534            let s = ConcurrentShardedStack::with_concurrency(4);
535            for (shard, panic) in [(first_shard, false), (first_shard, true), (3, false)] {
536                THREAD_ID.with(|id| id.set(shard));
537                assert!(
538                    s.push(Payload {
539                        panic,
540                        drops: Arc::clone(&drops)
541                    })
542                    .is_ok()
543                );
544            }
545            assert!(catch_unwind(AssertUnwindSafe(|| drop(s))).is_err());
546            assert_eq!(drops.load(Ordering::Relaxed), 3);
547        }
548    }
549
550    #[derive(Debug)]
551    struct DropCounter {
552        counter: Arc<AtomicUsize>,
553    }
554
555    impl DropCounter {
556        fn new(counter: Arc<AtomicUsize>) -> Self {
557            Self { counter }
558        }
559    }
560
561    impl Drop for DropCounter {
562        fn drop(&mut self) {
563            self.counter.fetch_add(1, Ordering::Relaxed);
564        }
565    }
566
567    #[test]
568    fn new_requires_power_of_two() {
569        let s = ConcurrentShardedStack::<usize>::with_concurrency(4);
570        assert_eq!(s.shard_count(), 4);
571    }
572
573    #[test]
574    #[should_panic]
575    fn new_panics_if_not_power_of_two() {
576        let _ = ConcurrentShardedStack::<usize>::with_concurrency(3);
577    }
578
579    #[test]
580    fn push_pop_single_thread() {
581        let s = ConcurrentShardedStack::with_concurrency(4);
582
583        s.push(1).unwrap();
584        s.push(2).unwrap();
585        s.push(3).unwrap();
586
587        assert_eq!(s.pop().unwrap(), 3);
588        assert_eq!(s.pop().unwrap(), 2);
589        assert_eq!(s.pop().unwrap(), 1);
590
591        assert_eq!(s.pop(), Err(PopError::Empty));
592    }
593
594    #[test]
595    fn close_works() {
596        let s = ConcurrentShardedStack::with_concurrency(4);
597
598        assert!(s.push(1).is_ok());
599
600        assert!(s.close());
601        assert!(!s.close());
602
603        assert_eq!(s.push(2), Err(PushError::Closed(2)));
604
605        assert_eq!(s.pop().unwrap(), 1);
606        assert_eq!(s.pop(), Err(PopError::Closed));
607    }
608
609    #[test]
610    fn multi_thread_push_pop() {
611        let s = Arc::new(ConcurrentShardedStack::with_concurrency(8));
612
613        let threads = 8;
614        // Miri executes far slower, so use a much smaller workload there.
615        #[cfg(miri)]
616        let per_thread = 200;
617        #[cfg(not(miri))]
618        let per_thread = 10_000;
619
620        let mut handles = Vec::new();
621
622        for t in 0..threads {
623            let s = Arc::clone(&s);
624
625            handles.push(std::thread::spawn(move || {
626                for i in 0..per_thread {
627                    s.push(t * per_thread + i).unwrap();
628                }
629            }));
630        }
631
632        for handle in handles {
633            handle.join().unwrap();
634        }
635
636        let mut handles = Vec::new();
637
638        for _ in 0..threads {
639            let s = Arc::clone(&s);
640
641            handles.push(std::thread::spawn(move || {
642                let mut count = 0usize;
643
644                loop {
645                    match s.pop() {
646                        Ok(_) => count += 1,
647                        Err(PopError::Empty) => break,
648                        Err(PopError::Closed) => break,
649                    }
650                }
651
652                count
653            }));
654        }
655
656        let total: usize = handles.into_iter().map(|h| h.join().unwrap()).sum();
657
658        assert_eq!(total, threads * per_thread);
659    }
660
661    #[test]
662    fn close_after_drain_returns_closed() {
663        let s = ConcurrentShardedStack::with_concurrency(4);
664
665        for i in 0..100 {
666            s.push(i).unwrap();
667        }
668
669        assert!(s.close());
670
671        let mut count = 0;
672
673        loop {
674            match s.pop() {
675                Ok(_) => count += 1,
676                Err(PopError::Empty) => continue,
677                Err(PopError::Closed) => break,
678            }
679        }
680
681        assert_eq!(count, 100);
682    }
683
684    #[test]
685    fn popped_values_are_dropped_exactly_once() {
686        let counter = Arc::new(AtomicUsize::new(0));
687        let s = ConcurrentShardedStack::with_concurrency(4);
688
689        for _ in 0..50 {
690            s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
691        }
692
693        // Pop everything; each popped value should be dropped exactly once when
694        // it goes out of scope here.
695        let mut popped = 0;
696        while let Ok(value) = s.pop() {
697            drop(value);
698            popped += 1;
699        }
700
701        assert_eq!(popped, 50);
702
703        // Request reclamation; flush does not guarantee that every deferred
704        // callback runs here. Payloads must already have been dropped by pop.
705        drop(s);
706        epoch::pin().flush();
707
708        assert_eq!(counter.load(Ordering::Relaxed), 50);
709    }
710
711    #[test]
712    fn remaining_values_are_dropped_when_stack_is_dropped() {
713        let counter = Arc::new(AtomicUsize::new(0));
714
715        {
716            let s = ConcurrentShardedStack::with_concurrency(4);
717            for _ in 0..30 {
718                s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
719            }
720            // Drop the stack without popping; all 30 values must be dropped once.
721        }
722
723        assert_eq!(counter.load(Ordering::Relaxed), 30);
724    }
725
726    #[test]
727    fn partially_drained_stack_drops_each_value_once() {
728        let counter = Arc::new(AtomicUsize::new(0));
729
730        {
731            let s = ConcurrentShardedStack::with_concurrency(4);
732            for _ in 0..40 {
733                s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
734            }
735
736            for _ in 0..15 {
737                let _ = s.pop().unwrap();
738            }
739            // 15 dropped via pop, 25 remain to be dropped by the stack's Drop.
740        }
741
742        epoch::pin().flush();
743        assert_eq!(counter.load(Ordering::Relaxed), 40);
744    }
745
746    #[test]
747    fn concurrent_drop_counter_no_double_free() {
748        let counter = Arc::new(AtomicUsize::new(0));
749        let s = Arc::new(ConcurrentShardedStack::with_concurrency(4));
750
751        let threads = 4;
752        #[cfg(miri)]
753        let per_thread = 50;
754        #[cfg(not(miri))]
755        let per_thread = 200;
756
757        let mut handles = Vec::new();
758        for _ in 0..threads {
759            let s = Arc::clone(&s);
760            let counter = Arc::clone(&counter);
761            handles.push(std::thread::spawn(move || {
762                for _ in 0..per_thread {
763                    s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
764                }
765            }));
766        }
767        for h in handles {
768            h.join().unwrap();
769        }
770
771        let mut handles = Vec::new();
772        for _ in 0..threads {
773            let s = Arc::clone(&s);
774            handles.push(std::thread::spawn(move || {
775                let mut popped = 0;
776                while let Ok(value) = s.pop() {
777                    drop(value);
778                    popped += 1;
779                }
780                popped
781            }));
782        }
783
784        let total: usize = handles.into_iter().map(|h| h.join().unwrap()).sum();
785        assert_eq!(total, threads * per_thread);
786
787        drop(s);
788        epoch::pin().flush();
789        assert_eq!(counter.load(Ordering::Relaxed), threads * per_thread);
790    }
791
792    /// Wait until `cond` returns true, or panic with `label` after `timeout`.
793    /// Used by the loss-detection tests to turn "popper hangs forever because
794    /// an element is invisible" into an explicit, debuggable failure rather
795    /// than a CI timeout.
796    fn wait_until<F: Fn() -> bool>(timeout: Duration, label: &str, cond: F) {
797        let start = Instant::now();
798        while !cond() {
799            if start.elapsed() > timeout {
800                panic!("{label}: condition not met within {timeout:?}");
801            }
802            std::thread::sleep(Duration::from_millis(5));
803        }
804    }
805
806    /// Pure-pusher / pure-popper split with **no** `close()`. Pushers map to a
807    /// disjoint set of shards from poppers, so the shards that hold the
808    /// pushed elements have no "local owner" that will ever pop them — every
809    /// element has to be reached by a popper whose local shard differs from
810    /// the pusher's, i.e. via the cross-shard scan in [`Self::pop`].
811    ///
812    /// This is the workload that exercises the worst case of the sharded
813    /// scan: there is no fast path to the elements (no popper-thread ever
814    /// hits its own shard for these pushes), and poppers must keep walking
815    /// the full XOR-mask order until the elements are drained. The test
816    /// asserts every pushed element is observed by some popper within a
817    /// generous timeout; otherwise it fails loudly.
818    ///
819    /// Skipped under Miri: this is a hardware-race stress test (busy-spin
820    /// poppers, no `close()`, watchdog measured in wall-clock seconds), and
821    /// Miri's deterministic cooperative scheduler neither exposes the race
822    /// window this is designed to catch nor finishes the workload in any
823    /// reasonable wall-clock budget. UB and data-race coverage for this
824    /// shape is handled by `no_element_loss_after_close_asymmetric`.
825    #[cfg_attr(miri, ignore)]
826    #[test]
827    fn no_element_loss_open_asymmetric() {
828        // Miri is too slow to hit this race repeatedly; keep workload tiny.
829        #[cfg(miri)]
830        let (n_pushers, n_poppers, per_pusher, rounds) = (2, 2, 200, 1);
831        #[cfg(not(miri))]
832        let (n_pushers, n_poppers, per_pusher, rounds) = (4, 12, 50_000, 4);
833
834        for round in 0..rounds {
835            let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(16));
836            let popped = Arc::new(AtomicUsize::new(0));
837            let pushed = Arc::new(AtomicUsize::new(0));
838            let stop = Arc::new(AtomicBool::new(false));
839            let total = n_pushers * per_pusher;
840
841            let mut handles = Vec::new();
842            for t in 0..n_pushers {
843                let s = Arc::clone(&s);
844                let pushed = Arc::clone(&pushed);
845                handles.push(std::thread::spawn(move || {
846                    for i in 0..per_pusher {
847                        s.push(t * per_pusher + i).unwrap();
848                        pushed.fetch_add(1, Ordering::Relaxed);
849                    }
850                }));
851            }
852
853            for _ in 0..n_poppers {
854                let s = Arc::clone(&s);
855                let popped = Arc::clone(&popped);
856                let stop = Arc::clone(&stop);
857                handles.push(std::thread::spawn(move || {
858                    while !stop.load(Ordering::Relaxed) {
859                        match s.pop() {
860                            Ok(_) => {
861                                popped.fetch_add(1, Ordering::Relaxed);
862                            }
863                            Err(PopError::Empty) => std::hint::spin_loop(),
864                            Err(PopError::Closed) => break,
865                        }
866                    }
867                }));
868            }
869
870            // 30 s is enormous for this workload (<100 ms in practice); only
871            // a real loss should ever exceed it.
872            wait_until(Duration::from_secs(30), "popper drain (open)", || {
873                popped.load(Ordering::Relaxed) >= total
874            });
875            stop.store(true, Ordering::Relaxed);
876
877            for h in handles {
878                h.join().unwrap();
879            }
880
881            let final_pushed = pushed.load(Ordering::Relaxed);
882            let final_popped = popped.load(Ordering::Relaxed);
883            assert_eq!(
884                final_popped, final_pushed,
885                "round {round}: popped {final_popped} != pushed {final_pushed}",
886            );
887        }
888    }
889
890    /// Same asymmetric split, but with the producer side `close()`ing the
891    /// stack once it has pushed everything. The post-`close()` drain must
892    /// catch every in-flight element: with no `close()`, a popper can race
893    /// indefinitely against pushers and keep observing `Empty` between
894    /// pushes, so closing turns the open-ended scan into a finite one.
895    #[test]
896    fn no_element_loss_after_close_asymmetric() {
897        #[cfg(miri)]
898        let (n_pushers, n_poppers, per_pusher, rounds) = (2, 2, 200, 1);
899        #[cfg(not(miri))]
900        let (n_pushers, n_poppers, per_pusher, rounds) = (4, 12, 50_000, 4);
901
902        for round in 0..rounds {
903            let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(16));
904            let popped = Arc::new(AtomicUsize::new(0));
905            let total = n_pushers * per_pusher;
906
907            let mut handles = Vec::new();
908            for t in 0..n_pushers {
909                let s = Arc::clone(&s);
910                handles.push(std::thread::spawn(move || {
911                    for i in 0..per_pusher {
912                        s.push(t * per_pusher + i).unwrap();
913                    }
914                }));
915            }
916
917            for _ in 0..n_poppers {
918                let s = Arc::clone(&s);
919                let popped = Arc::clone(&popped);
920                handles.push(std::thread::spawn(move || {
921                    loop {
922                        match s.pop() {
923                            Ok(_) => {
924                                popped.fetch_add(1, Ordering::Relaxed);
925                            }
926                            Err(PopError::Empty) => std::hint::spin_loop(),
927                            Err(PopError::Closed) => break,
928                        }
929                    }
930                }));
931            }
932
933            // Wait for pushers to finish, then close. Poppers continue
934            // draining until they observe Closed.
935            let pusher_handles: Vec<_> = handles.drain(..n_pushers).collect();
936            for h in pusher_handles {
937                h.join().unwrap();
938            }
939            s.close();
940
941            for h in handles {
942                h.join().unwrap();
943            }
944
945            assert_eq!(
946                popped.load(Ordering::Relaxed),
947                total,
948                "round {round}: drain after close lost elements",
949            );
950        }
951    }
952
953    /// Lopsided shard count: many shards, few threads. Most shards are owned
954    /// by nobody, so a popper only reaches the elements pushed there via the
955    /// cross-shard scan in [`Self::pop`] (its own local shard is empty for
956    /// those pushers). Catches loss via the cross-shard scan path.
957    #[test]
958    fn no_element_loss_few_threads_many_shards() {
959        #[cfg(miri)]
960        let (n_pushers, n_poppers, per_pusher, shards) = (2, 1, 100, 8);
961        #[cfg(not(miri))]
962        let (n_pushers, n_poppers, per_pusher, shards) = (2, 1, 100_000, 32);
963
964        let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(shards));
965        let popped = Arc::new(AtomicUsize::new(0));
966        let total = n_pushers * per_pusher;
967
968        let mut handles = Vec::new();
969        for _ in 0..n_pushers {
970            let s = Arc::clone(&s);
971            handles.push(std::thread::spawn(move || {
972                for i in 0..per_pusher {
973                    s.push(i).unwrap();
974                }
975            }));
976        }
977
978        for _ in 0..n_poppers {
979            let s = Arc::clone(&s);
980            let popped = Arc::clone(&popped);
981            handles.push(std::thread::spawn(move || {
982                let start = Instant::now();
983                while popped.load(Ordering::Relaxed) < total {
984                    match s.pop() {
985                        Ok(_) => {
986                            popped.fetch_add(1, Ordering::Relaxed);
987                        }
988                        Err(PopError::Empty) => std::hint::spin_loop(),
989                        Err(PopError::Closed) => break,
990                    }
991                    if start.elapsed() > Duration::from_secs(30) {
992                        panic!(
993                            "popper stuck: popped {} of {}",
994                            popped.load(Ordering::Relaxed),
995                            total,
996                        );
997                    }
998                }
999            }));
1000        }
1001
1002        for h in handles {
1003            h.join().unwrap();
1004        }
1005        assert_eq!(popped.load(Ordering::Relaxed), total);
1006    }
1007}