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 stack 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    Empty,
74    Closed,
75}
76
77impl fmt::Display for PopError {
78    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
79        match self {
80            PopError::Empty => write!(f, "stack is empty"),
81            PopError::Closed => write!(f, "stack is closed"),
82        }
83    }
84}
85
86impl std::error::Error for PopError {}
87
88struct Node<T> {
89    value: ManuallyDrop<T>,
90    next: Atomic<Node<T>>,
91}
92
93impl<T> Node<T> {
94    fn new(value: T) -> Self {
95        Self {
96            value: ManuallyDrop::new(value),
97            next: Atomic::null(),
98        }
99    }
100}
101
102enum ShardPopResult<T> {
103    Popped(T),
104    Empty,
105    EmptyAndClosed,
106}
107
108/// Concurrent sharded Treiber stack.
109pub struct ConcurrentShardedStack<T> {
110    shards: Box<[CachePadded<Atomic<Node<T>>>]>,
111    shard_index_mask: usize,
112}
113
114unsafe impl<T: Send> Send for ConcurrentShardedStack<T> {}
115unsafe impl<T: Send> Sync for ConcurrentShardedStack<T> {}
116
117impl<T> Default for ConcurrentShardedStack<T> {
118    fn default() -> Self {
119        Self::new()
120    }
121}
122
123impl<T> ConcurrentShardedStack<T> {
124    /// Creates a stack using `available_parallelism()` as concurrency hint.
125    pub fn new() -> Self {
126        let concurrency = thread::available_parallelism()
127            .map(|n| n.get().next_power_of_two())
128            .unwrap_or(4);
129
130        Self::with_concurrency(concurrency)
131    }
132
133    /// Creates a stack with exact shard count.
134    ///
135    /// Panics if:
136    ///
137    /// - `shard_count == 0`
138    /// - `shard_count` is not power of two
139    pub fn with_concurrency(shard_count: usize) -> Self {
140        assert!(shard_count > 0, "shard_count must be non-zero");
141
142        assert!(
143            shard_count.is_power_of_two(),
144            "shard_count must be a power of two"
145        );
146
147        let mut shards = Vec::with_capacity(shard_count);
148
149        for _ in 0..shard_count {
150            shards.push(CachePadded::new(Atomic::null()));
151        }
152
153        Self {
154            shards: shards.into_boxed_slice(),
155            shard_index_mask: shard_count - 1,
156        }
157    }
158
159    /// Pushes a value into the stack.
160    ///
161    /// Returns `Err(PushError::Closed(value))` if the stack is already closed.
162    pub fn push(&self, value: T) -> Result<(), PushError<T>> {
163        let shard_index = self.current_shard_index();
164        let shard = &self.shards[shard_index];
165
166        let guard = &epoch::pin();
167        let mut node = Owned::new(Node::new(value));
168
169        loop {
170            let head = shard.load(Ordering::Acquire, guard);
171
172            if head.tag() == CLOSED_TAG {
173                let node = node.into_box();
174                let value = unsafe { ptr::read(&*node.value) };
175                return Err(PushError::Closed(value));
176            }
177
178            node.next.store(head, Ordering::Relaxed);
179
180            match shard.compare_exchange_weak(
181                head,
182                node,
183                Ordering::Release,
184                Ordering::Relaxed,
185                guard,
186            ) {
187                Ok(_) => return Ok(()),
188                Err(err) => {
189                    node = err.new;
190                    spin_loop();
191                }
192            }
193        }
194    }
195
196    /// Pops a value from the stack non-blocking.
197    ///
198    /// Scan order:
199    ///
200    /// - first scan the current thread's own shard;
201    /// - then scan the shard whose last binary bit differs;
202    /// - then scan shards whose next binary bit differs;
203    /// - continue widening the differing-bit window until all shards are scanned.
204    ///
205    /// For example, with 8 shards and local shard `start`, the XOR masks are:
206    ///
207    /// ```text
208    /// 0,
209    /// 1,
210    /// 2, 3,
211    /// 4, 5, 6, 7
212    /// ```
213    ///
214    /// So the actual scan order is:
215    ///
216    /// ```text
217    /// start,
218    /// start ^ 1,
219    /// start ^ 2, start ^ 3,
220    /// start ^ 4, start ^ 5, start ^ 6, start ^ 7
221    /// ```
222    ///
223    /// Returns `Err(PopError::Empty)` if no element is found and at least one
224    /// shard is still observed open.
225    ///
226    /// Returns `Err(PopError::Closed)` if no element is found and every shard
227    /// is observed closed.
228    pub fn pop(&self) -> Result<T, PopError> {
229        let guard = &epoch::pin();
230        let start = self.current_shard_index();
231        let shard_count = self.shards.len();
232
233        let mut all_closed = true;
234
235        for mask in 0..shard_count {
236            let index = start ^ mask;
237
238            match self.pop_one(index, guard) {
239                ShardPopResult::Popped(value) => return Ok(value),
240                ShardPopResult::Empty => {
241                    all_closed = false;
242                }
243                ShardPopResult::EmptyAndClosed => {}
244            }
245        }
246
247        if all_closed {
248            Err(PopError::Closed)
249        } else {
250            Err(PopError::Empty)
251        }
252    }
253
254    /// Closes the stack. Existing elements can still be popped.
255    pub fn close(&self) -> bool {
256        let guard = &epoch::pin();
257        let mut changed = false;
258
259        for shard in self.shards.iter() {
260            loop {
261                let head = shard.load(Ordering::Acquire, guard);
262
263                if head.tag() == CLOSED_TAG {
264                    break;
265                }
266
267                match shard.compare_exchange_weak(
268                    head,
269                    head.with_tag(CLOSED_TAG),
270                    Ordering::AcqRel,
271                    Ordering::Relaxed,
272                    guard,
273                ) {
274                    Ok(_) => {
275                        changed = true;
276                        break;
277                    }
278                    Err(_) => spin_loop(),
279                }
280            }
281        }
282
283        changed
284    }
285
286    /// Checks if the stack is closed.
287    pub fn is_closed(&self) -> bool {
288        let guard = &epoch::pin();
289        self.all_shards_closed(guard)
290    }
291
292    pub fn shard_count(&self) -> usize {
293        self.shards.len()
294    }
295
296    fn current_shard_index(&self) -> usize {
297        current_thread_id() & self.shard_index_mask
298    }
299
300    /// Pops from one shard.
301    ///
302    /// This function loops until the shard produces a definite result:
303    ///
304    /// - popped one value;
305    /// - or the shard is observed empty.
306    ///
307    /// CAS failures are retried indefinitely for this shard. There is no fixed
308    /// retry budget anymore.
309    ///
310    /// Returns:
311    ///
312    /// - `value: Some(T)` if a value was popped;
313    /// - `value: None` if this shard is currently empty;
314    /// - `closed` indicates whether this shard was observed closed.
315    fn pop_one(&self, index: usize, guard: &Guard) -> ShardPopResult<T> {
316        let shard = &self.shards[index];
317
318        loop {
319            let head = shard.load(Ordering::Acquire, guard);
320            let closed = head.tag() == CLOSED_TAG;
321
322            if head.is_null() {
323                return if closed {
324                    ShardPopResult::EmptyAndClosed
325                } else {
326                    ShardPopResult::Empty
327                };
328            }
329
330            let head_ref = unsafe { head.deref() };
331
332            // `head` was published by a Release CAS that we synchronized with
333            // via the Acquire load above, so the node's fields are visible.
334            let next = head_ref.next.load(Ordering::Relaxed, guard);
335
336            // Preserve the CLOSED tag when popping from a closed shard.
337            let new_head = next.with_tag(head.tag());
338
339            match shard.compare_exchange(head, new_head, Ordering::AcqRel, Ordering::Relaxed, guard)
340            {
341                Ok(_) => {
342                    // Move the value out of the popped node. The node itself
343                    // is reclaimed later by epoch GC; because `value` is inside
344                    // `ManuallyDrop<T>`, deferred destruction will not drop it again.
345                    let value = unsafe { ptr::read(&*head_ref.value) };
346
347                    unsafe {
348                        guard.defer_destroy(head.with_tag(0));
349                    }
350
351                    return ShardPopResult::Popped(value);
352                }
353                Err(_) => {
354                    spin_loop();
355                }
356            }
357        }
358    }
359
360    fn all_shards_closed(&self, guard: &Guard) -> bool {
361        self.shards
362            .iter()
363            .all(|shard| shard.load(Ordering::Acquire, guard).tag() == CLOSED_TAG)
364    }
365}
366
367impl<T> Drop for ConcurrentShardedStack<T> {
368    fn drop(&mut self) {
369        let guard = &epoch::pin();
370
371        for shard in self.shards.iter() {
372            let mut current = shard.load(Ordering::Relaxed, guard);
373
374            while !current.is_null() {
375                unsafe {
376                    let raw = current.as_raw() as *mut Node<T>;
377                    let next = (*raw).next.load(Ordering::Relaxed, guard);
378
379                    let mut node = Box::from_raw(raw);
380
381                    // The value was never popped, so we are responsible for
382                    // dropping it here. It lives inside a `ManuallyDrop<T>`.
383                    ManuallyDrop::drop(&mut node.value);
384
385                    drop(node);
386
387                    current = next;
388                }
389            }
390        }
391    }
392}
393
394#[cfg(test)]
395mod tests {
396    use super::*;
397    use std::sync::Arc;
398    use std::sync::atomic::{AtomicBool, AtomicUsize};
399    use std::time::{Duration, Instant};
400
401    #[derive(Debug)]
402    struct DropCounter {
403        counter: Arc<AtomicUsize>,
404    }
405
406    impl DropCounter {
407        fn new(counter: Arc<AtomicUsize>) -> Self {
408            Self { counter }
409        }
410    }
411
412    impl Drop for DropCounter {
413        fn drop(&mut self) {
414            self.counter.fetch_add(1, Ordering::Relaxed);
415        }
416    }
417
418    #[test]
419    fn new_requires_power_of_two() {
420        let s = ConcurrentShardedStack::<usize>::with_concurrency(4);
421        assert_eq!(s.shard_count(), 4);
422    }
423
424    #[test]
425    #[should_panic]
426    fn new_panics_if_not_power_of_two() {
427        let _ = ConcurrentShardedStack::<usize>::with_concurrency(3);
428    }
429
430    #[test]
431    fn push_pop_single_thread() {
432        let s = ConcurrentShardedStack::with_concurrency(4);
433
434        s.push(1).unwrap();
435        s.push(2).unwrap();
436        s.push(3).unwrap();
437
438        assert_eq!(s.pop().unwrap(), 3);
439        assert_eq!(s.pop().unwrap(), 2);
440        assert_eq!(s.pop().unwrap(), 1);
441
442        assert_eq!(s.pop(), Err(PopError::Empty));
443    }
444
445    #[test]
446    fn close_works() {
447        let s = ConcurrentShardedStack::with_concurrency(4);
448
449        assert!(s.push(1).is_ok());
450
451        assert!(s.close());
452        assert!(!s.close());
453
454        assert_eq!(s.push(2), Err(PushError::Closed(2)));
455
456        assert_eq!(s.pop().unwrap(), 1);
457        assert_eq!(s.pop(), Err(PopError::Closed));
458    }
459
460    #[test]
461    fn multi_thread_push_pop() {
462        let s = Arc::new(ConcurrentShardedStack::with_concurrency(8));
463
464        let threads = 8;
465        // Miri executes far slower, so use a much smaller workload there.
466        #[cfg(miri)]
467        let per_thread = 200;
468        #[cfg(not(miri))]
469        let per_thread = 10_000;
470
471        let mut handles = Vec::new();
472
473        for t in 0..threads {
474            let s = Arc::clone(&s);
475
476            handles.push(std::thread::spawn(move || {
477                for i in 0..per_thread {
478                    s.push(t * per_thread + i).unwrap();
479                }
480            }));
481        }
482
483        for handle in handles {
484            handle.join().unwrap();
485        }
486
487        let mut handles = Vec::new();
488
489        for _ in 0..threads {
490            let s = Arc::clone(&s);
491
492            handles.push(std::thread::spawn(move || {
493                let mut count = 0usize;
494
495                loop {
496                    match s.pop() {
497                        Ok(_) => count += 1,
498                        Err(PopError::Empty) => break,
499                        Err(PopError::Closed) => break,
500                    }
501                }
502
503                count
504            }));
505        }
506
507        let total: usize = handles.into_iter().map(|h| h.join().unwrap()).sum();
508
509        assert_eq!(total, threads * per_thread);
510    }
511
512    #[test]
513    fn close_after_drain_returns_closed() {
514        let s = ConcurrentShardedStack::with_concurrency(4);
515
516        for i in 0..100 {
517            s.push(i).unwrap();
518        }
519
520        assert!(s.close());
521
522        let mut count = 0;
523
524        loop {
525            match s.pop() {
526                Ok(_) => count += 1,
527                Err(PopError::Empty) => continue,
528                Err(PopError::Closed) => break,
529            }
530        }
531
532        assert_eq!(count, 100);
533    }
534
535    #[test]
536    fn popped_values_are_dropped_exactly_once() {
537        let counter = Arc::new(AtomicUsize::new(0));
538        let s = ConcurrentShardedStack::with_concurrency(4);
539
540        for _ in 0..50 {
541            s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
542        }
543
544        // Pop everything; each popped value should be dropped exactly once when
545        // it goes out of scope here.
546        let mut popped = 0;
547        while let Ok(value) = s.pop() {
548            drop(value);
549            popped += 1;
550        }
551
552        assert_eq!(popped, 50);
553
554        // Force any deferred reclamation to run. Even after reclamation, the
555        // count must stay at exactly 50 (no double-drop from `defer_destroy`).
556        drop(s);
557        epoch::pin().flush();
558
559        assert_eq!(counter.load(Ordering::Relaxed), 50);
560    }
561
562    #[test]
563    fn remaining_values_are_dropped_when_stack_is_dropped() {
564        let counter = Arc::new(AtomicUsize::new(0));
565
566        {
567            let s = ConcurrentShardedStack::with_concurrency(4);
568            for _ in 0..30 {
569                s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
570            }
571            // Drop the stack without popping; all 30 values must be dropped once.
572        }
573
574        assert_eq!(counter.load(Ordering::Relaxed), 30);
575    }
576
577    #[test]
578    fn partially_drained_stack_drops_each_value_once() {
579        let counter = Arc::new(AtomicUsize::new(0));
580
581        {
582            let s = ConcurrentShardedStack::with_concurrency(4);
583            for _ in 0..40 {
584                s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
585            }
586
587            for _ in 0..15 {
588                let _ = s.pop().unwrap();
589            }
590            // 15 dropped via pop, 25 remain to be dropped by the stack's Drop.
591        }
592
593        epoch::pin().flush();
594        assert_eq!(counter.load(Ordering::Relaxed), 40);
595    }
596
597    #[test]
598    fn concurrent_drop_counter_no_double_free() {
599        let counter = Arc::new(AtomicUsize::new(0));
600        let s = Arc::new(ConcurrentShardedStack::with_concurrency(4));
601
602        let threads = 4;
603        #[cfg(miri)]
604        let per_thread = 50;
605        #[cfg(not(miri))]
606        let per_thread = 200;
607
608        let mut handles = Vec::new();
609        for _ in 0..threads {
610            let s = Arc::clone(&s);
611            let counter = Arc::clone(&counter);
612            handles.push(std::thread::spawn(move || {
613                for _ in 0..per_thread {
614                    s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
615                }
616            }));
617        }
618        for h in handles {
619            h.join().unwrap();
620        }
621
622        let mut handles = Vec::new();
623        for _ in 0..threads {
624            let s = Arc::clone(&s);
625            handles.push(std::thread::spawn(move || {
626                let mut popped = 0;
627                while let Ok(value) = s.pop() {
628                    drop(value);
629                    popped += 1;
630                }
631                popped
632            }));
633        }
634
635        let total: usize = handles.into_iter().map(|h| h.join().unwrap()).sum();
636        assert_eq!(total, threads * per_thread);
637
638        drop(s);
639        epoch::pin().flush();
640        assert_eq!(counter.load(Ordering::Relaxed), threads * per_thread);
641    }
642
643    /// Wait until `cond` returns true, or panic with `label` after `timeout`.
644    /// Used by the loss-detection tests to turn "popper hangs forever because
645    /// an element is invisible" into an explicit, debuggable failure rather
646    /// than a CI timeout.
647    fn wait_until<F: Fn() -> bool>(timeout: Duration, label: &str, cond: F) {
648        let start = Instant::now();
649        while !cond() {
650            if start.elapsed() > timeout {
651                panic!("{label}: condition not met within {timeout:?}");
652            }
653            std::thread::sleep(Duration::from_millis(5));
654        }
655    }
656
657    /// Pure-pusher / pure-popper split with **no** `close()`. Pushers map to a
658    /// disjoint set of shards from poppers, so the shards that hold the
659    /// pushed elements have no "local owner" that will ever pop them — every
660    /// element has to be reached by a popper whose local shard differs from
661    /// the pusher's, i.e. via the cross-shard scan in [`Self::pop`].
662    ///
663    /// This is the workload that exercises the worst case of the sharded
664    /// scan: there is no fast path to the elements (no popper-thread ever
665    /// hits its own shard for these pushes), and poppers must keep walking
666    /// the full XOR-mask order until the elements are drained. The test
667    /// asserts every pushed element is observed by some popper within a
668    /// generous timeout; otherwise it fails loudly.
669    ///
670    /// Skipped under Miri: this is a hardware-race stress test (busy-spin
671    /// poppers, no `close()`, watchdog measured in wall-clock seconds), and
672    /// Miri's deterministic cooperative scheduler neither exposes the race
673    /// window this is designed to catch nor finishes the workload in any
674    /// reasonable wall-clock budget. UB and data-race coverage for this
675    /// shape is handled by `no_element_loss_after_close_asymmetric`.
676    #[cfg_attr(miri, ignore)]
677    #[test]
678    fn no_element_loss_open_asymmetric() {
679        // Miri is too slow to hit this race repeatedly; keep workload tiny.
680        #[cfg(miri)]
681        let (n_pushers, n_poppers, per_pusher, rounds) = (2, 2, 200, 1);
682        #[cfg(not(miri))]
683        let (n_pushers, n_poppers, per_pusher, rounds) = (4, 12, 50_000, 4);
684
685        for round in 0..rounds {
686            let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(16));
687            let popped = Arc::new(AtomicUsize::new(0));
688            let pushed = Arc::new(AtomicUsize::new(0));
689            let stop = Arc::new(AtomicBool::new(false));
690            let total = n_pushers * per_pusher;
691
692            let mut handles = Vec::new();
693            for t in 0..n_pushers {
694                let s = Arc::clone(&s);
695                let pushed = Arc::clone(&pushed);
696                handles.push(std::thread::spawn(move || {
697                    for i in 0..per_pusher {
698                        s.push(t * per_pusher + i).unwrap();
699                        pushed.fetch_add(1, Ordering::Relaxed);
700                    }
701                }));
702            }
703
704            for _ in 0..n_poppers {
705                let s = Arc::clone(&s);
706                let popped = Arc::clone(&popped);
707                let stop = Arc::clone(&stop);
708                handles.push(std::thread::spawn(move || {
709                    while !stop.load(Ordering::Relaxed) {
710                        match s.pop() {
711                            Ok(_) => {
712                                popped.fetch_add(1, Ordering::Relaxed);
713                            }
714                            Err(PopError::Empty) => std::hint::spin_loop(),
715                            Err(PopError::Closed) => break,
716                        }
717                    }
718                }));
719            }
720
721            // 30 s is enormous for this workload (<100 ms in practice); only
722            // a real loss should ever exceed it.
723            wait_until(Duration::from_secs(30), "popper drain (open)", || {
724                popped.load(Ordering::Relaxed) >= total
725            });
726            stop.store(true, Ordering::Relaxed);
727
728            for h in handles {
729                h.join().unwrap();
730            }
731
732            let final_pushed = pushed.load(Ordering::Relaxed);
733            let final_popped = popped.load(Ordering::Relaxed);
734            assert_eq!(
735                final_popped, final_pushed,
736                "round {round}: popped {final_popped} != pushed {final_pushed}",
737            );
738        }
739    }
740
741    /// Same asymmetric split, but with the producer side `close()`ing the
742    /// stack once it has pushed everything. The post-`close()` drain must
743    /// catch every in-flight element: with no `close()`, a popper can race
744    /// indefinitely against pushers and keep observing `Empty` between
745    /// pushes, so closing turns the open-ended scan into a finite one.
746    #[test]
747    fn no_element_loss_after_close_asymmetric() {
748        #[cfg(miri)]
749        let (n_pushers, n_poppers, per_pusher, rounds) = (2, 2, 200, 1);
750        #[cfg(not(miri))]
751        let (n_pushers, n_poppers, per_pusher, rounds) = (4, 12, 50_000, 4);
752
753        for round in 0..rounds {
754            let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(16));
755            let popped = Arc::new(AtomicUsize::new(0));
756            let total = n_pushers * per_pusher;
757
758            let mut handles = Vec::new();
759            for t in 0..n_pushers {
760                let s = Arc::clone(&s);
761                handles.push(std::thread::spawn(move || {
762                    for i in 0..per_pusher {
763                        s.push(t * per_pusher + i).unwrap();
764                    }
765                }));
766            }
767
768            for _ in 0..n_poppers {
769                let s = Arc::clone(&s);
770                let popped = Arc::clone(&popped);
771                handles.push(std::thread::spawn(move || {
772                    loop {
773                        match s.pop() {
774                            Ok(_) => {
775                                popped.fetch_add(1, Ordering::Relaxed);
776                            }
777                            Err(PopError::Empty) => std::hint::spin_loop(),
778                            Err(PopError::Closed) => break,
779                        }
780                    }
781                }));
782            }
783
784            // Wait for pushers to finish, then close. Poppers continue
785            // draining until they observe Closed.
786            let pusher_handles: Vec<_> = handles.drain(..n_pushers).collect();
787            for h in pusher_handles {
788                h.join().unwrap();
789            }
790            s.close();
791
792            for h in handles {
793                h.join().unwrap();
794            }
795
796            assert_eq!(
797                popped.load(Ordering::Relaxed),
798                total,
799                "round {round}: drain after close lost elements",
800            );
801        }
802    }
803
804    /// Lopsided shard count: many shards, few threads. Most shards are owned
805    /// by nobody, so a popper only reaches the elements pushed there via the
806    /// cross-shard scan in [`Self::pop`] (its own local shard is empty for
807    /// those pushers). Catches loss via the cross-shard scan path.
808    #[test]
809    fn no_element_loss_few_threads_many_shards() {
810        #[cfg(miri)]
811        let (n_pushers, n_poppers, per_pusher, shards) = (2, 1, 100, 8);
812        #[cfg(not(miri))]
813        let (n_pushers, n_poppers, per_pusher, shards) = (2, 1, 100_000, 32);
814
815        let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(shards));
816        let popped = Arc::new(AtomicUsize::new(0));
817        let total = n_pushers * per_pusher;
818
819        let mut handles = Vec::new();
820        for _ in 0..n_pushers {
821            let s = Arc::clone(&s);
822            handles.push(std::thread::spawn(move || {
823                for i in 0..per_pusher {
824                    s.push(i).unwrap();
825                }
826            }));
827        }
828
829        for _ in 0..n_poppers {
830            let s = Arc::clone(&s);
831            let popped = Arc::clone(&popped);
832            handles.push(std::thread::spawn(move || {
833                let start = Instant::now();
834                while popped.load(Ordering::Relaxed) < total {
835                    match s.pop() {
836                        Ok(_) => {
837                            popped.fetch_add(1, Ordering::Relaxed);
838                        }
839                        Err(PopError::Empty) => std::hint::spin_loop(),
840                        Err(PopError::Closed) => break,
841                    }
842                    if start.elapsed() > Duration::from_secs(30) {
843                        panic!(
844                            "popper stuck: popped {} of {}",
845                            popped.load(Ordering::Relaxed),
846                            total,
847                        );
848                    }
849                }
850            }));
851        }
852
853        for h in handles {
854            h.join().unwrap();
855        }
856        assert_eq!(popped.load(Ordering::Relaxed), total);
857    }
858}