concurrent_sharded_stack/
lib.rs1use 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 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
108pub 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 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 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 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 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 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 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 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 let next = head_ref.next.load(Ordering::Relaxed, guard);
335
336 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 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 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 #[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 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 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 }
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 }
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 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 #[cfg_attr(miri, ignore)]
677 #[test]
678 fn no_element_loss_open_asymmetric() {
679 #[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 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 #[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 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 #[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}