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::{AtomicBool, AtomicUsize, Ordering};
31use std::thread;
32
33static NEXT_THREAD_ID: AtomicUsize = AtomicUsize::new(0);
34
35thread_local! {
36    static THREAD_ID: Cell<usize> = Cell::new(
37        NEXT_THREAD_ID.fetch_add(1, Ordering::Relaxed)
38    );
39}
40
41fn current_thread_id() -> usize {
42    THREAD_ID.with(Cell::get)
43}
44
45#[derive(Debug, PartialEq, Eq)]
46pub enum PushError<T> {
47    /// The stack has been closed.
48    Closed(T),
49}
50
51impl<T> PushError<T> {
52    pub fn into_inner(self) -> T {
53        match self {
54            PushError::Closed(v) => v,
55        }
56    }
57}
58
59impl<T> fmt::Display for PushError<T> {
60    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
61        match self {
62            PushError::Closed(_) => write!(f, "stack is closed"),
63        }
64    }
65}
66
67impl<T: fmt::Debug> std::error::Error for PushError<T> {}
68
69#[derive(Debug, Clone, Copy, PartialEq, Eq)]
70pub enum PopError {
71    Empty,
72    Closed,
73}
74
75impl fmt::Display for PopError {
76    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
77        match self {
78            PopError::Empty => write!(f, "stack is empty"),
79            PopError::Closed => write!(f, "stack is closed"),
80        }
81    }
82}
83
84impl std::error::Error for PopError {}
85
86struct Node<T> {
87    value: ManuallyDrop<T>,
88    next: Atomic<Node<T>>,
89}
90
91impl<T> Node<T> {
92    fn new(value: T) -> Self {
93        Self {
94            value: ManuallyDrop::new(value),
95            next: Atomic::null(),
96        }
97    }
98}
99
100/// Concurrent sharded Treiber stack.
101pub struct ConcurrentShardedStack<T> {
102    shards: Box<[CachePadded<Atomic<Node<T>>>]>,
103
104    /// Bitmap for hinting.
105    /// Both `1` and `0` are just meaning that there may be or may not be an element in the corresponding shard.
106    bitmap: AtomicUsize,
107
108    shard_index_mask: usize,
109
110    closed: AtomicBool,
111}
112
113unsafe impl<T: Send> Send for ConcurrentShardedStack<T> {}
114unsafe impl<T: Send> Sync for ConcurrentShardedStack<T> {}
115
116impl<T> Default for ConcurrentShardedStack<T> {
117    fn default() -> Self {
118        Self::new()
119    }
120}
121
122impl<T> ConcurrentShardedStack<T> {
123    /// Creates a stack using `available_parallelism()` as concurrency hint.
124    pub fn new() -> Self {
125        let concurrency = thread::available_parallelism()
126            .map(|n| n.get().next_power_of_two().min(usize::BITS as usize))
127            .unwrap_or(4);
128
129        Self::with_concurrency(concurrency)
130    }
131
132    /// Creates a stack with exact shard count.
133    ///
134    /// Panics if:
135    ///
136    /// - `shard_count == 0`
137    /// - `shard_count` is not power of two
138    /// - `shard_count > usize::BITS`
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        assert!(
148            shard_count <= usize::BITS as usize,
149            "shard_count must not exceed usize::BITS"
150        );
151
152        let mut shards = Vec::with_capacity(shard_count);
153
154        for _ in 0..shard_count {
155            shards.push(CachePadded::new(Atomic::null()));
156        }
157
158        Self {
159            shards: shards.into_boxed_slice(),
160            bitmap: AtomicUsize::new(0),
161            shard_index_mask: shard_count - 1,
162            closed: AtomicBool::new(false),
163        }
164    }
165
166    /// Pushes a value into the stack.
167    ///
168    /// Returns `Err(PushError::Closed(value))` if the stack is already closed.
169    pub fn push(&self, value: T) -> Result<(), PushError<T>> {
170        if self.closed.load(Ordering::Acquire) {
171            return Err(PushError::Closed(value));
172        }
173
174        let shard_index = self.current_shard_index();
175        let shard = &self.shards[shard_index];
176        let bit = 1usize << shard_index;
177
178        let guard = &epoch::pin();
179        let mut node = Owned::new(Node::new(value));
180
181        loop {
182            let head = shard.load(Ordering::Acquire, guard);
183
184            node.next.store(head, Ordering::Relaxed);
185
186            match shard.compare_exchange_weak(
187                head,
188                node,
189                Ordering::Release,
190                Ordering::Acquire,
191                guard,
192            ) {
193                Ok(_) => {
194                    if self.bitmap.load(Ordering::Relaxed) & bit == 0 {
195                        self.bitmap.fetch_or(bit, Ordering::Release);
196                    }
197                    return Ok(());
198                }
199                Err(err) => {
200                    node = err.new;
201                    spin_loop();
202                }
203            }
204        }
205    }
206
207    /// Pops a value from the stack non-blocking.
208    ///
209    /// Returns `Err(PopError::Empty)` if the stack is empty.
210    /// Returns `Err(PopError::Closed)` if the stack is empty and closed.
211    pub fn pop(&self) -> Result<T, PopError> {
212        let guard = &epoch::pin();
213
214        let start = self.current_shard_index();
215        let shard_count = self.shards.len();
216
217        // 1. Current shard first.
218        if let Some(value) = self.try_pop_from_shard(start, guard) {
219            return Ok(value);
220        }
221
222        // 2. Bitmap-guided search.
223        let bits = self.bitmap.load(Ordering::Acquire);
224
225        if bits != 0 {
226            for offset in 1..shard_count {
227                let index = (start + offset) & self.shard_index_mask;
228
229                if bits & 1usize << index == 0 {
230                    continue;
231                }
232
233                if let Some(value) = self.try_pop_from_shard(index, guard) {
234                    return Ok(value);
235                }
236            }
237        }
238
239        // 3. Fallback.
240        for offset in 1..=shard_count {
241            let index = (start + offset) & self.shard_index_mask;
242
243            if let Some(value) = self.try_pop_from_shard(index, guard) {
244                return Ok(value);
245            }
246        }
247
248        if self.closed.load(Ordering::Acquire) {
249            Err(PopError::Closed)
250        } else {
251            Err(PopError::Empty)
252        }
253    }
254
255    /// Closes the stack, existing elements can still be popped.
256    pub fn close(&self) -> bool {
257        self.closed
258            .compare_exchange(false, true, Ordering::AcqRel, Ordering::Acquire)
259            .is_ok()
260    }
261
262    /// Checks if the stack is closed.
263    pub fn is_closed(&self) -> bool {
264        self.closed.load(Ordering::Acquire)
265    }
266
267    pub fn shard_count(&self) -> usize {
268        self.shards.len()
269    }
270
271    fn current_shard_index(&self) -> usize {
272        current_thread_id() & self.shard_index_mask
273    }
274
275    fn try_pop_from_shard(&self, index: usize, guard: &Guard) -> Option<T> {
276        let shard = &self.shards[index];
277        let b = 1usize << index;
278
279        loop {
280            let head = shard.load(Ordering::Acquire, guard);
281
282            if head.is_null() {
283                // Weak hint clearing.
284                self.bitmap.fetch_and(!b, Ordering::AcqRel);
285                return None;
286            }
287
288            let head_ref = unsafe { head.deref() };
289            let next = head_ref.next.load(Ordering::Acquire, guard);
290
291            match shard.compare_exchange_weak(
292                head,
293                next,
294                Ordering::AcqRel,
295                Ordering::Acquire,
296                guard,
297            ) {
298                Ok(_) => {
299                    if next.is_null() {
300                        // Weak hint clearing.
301                        self.bitmap.fetch_and(!b, Ordering::AcqRel);
302                    }
303
304                    // Move the value out of the popped node. The node itself is
305                    // reclaimed later by the epoch GC; because `value` is a
306                    // `ManuallyDrop<T>`, that deferred destruction will not drop
307                    // it again.
308                    let value = unsafe { ptr::read(&*head_ref.value) };
309
310                    unsafe {
311                        guard.defer_destroy(head);
312                    }
313
314                    return Some(value);
315                }
316                Err(_) => {
317                    spin_loop();
318                }
319            }
320        }
321    }
322}
323
324impl<T> Drop for ConcurrentShardedStack<T> {
325    fn drop(&mut self) {
326        let guard = &epoch::pin();
327
328        for shard in self.shards.iter() {
329            let mut current = shard.load(Ordering::Relaxed, guard);
330
331            while !current.is_null() {
332                unsafe {
333                    let raw = current.as_raw() as *mut Node<T>;
334                    let next = (*raw).next.load(Ordering::Relaxed, guard);
335
336                    let mut node = Box::from_raw(raw);
337                    // The value was never popped, so we are responsible for
338                    // dropping it here (it lives inside a `ManuallyDrop`).
339                    ManuallyDrop::drop(&mut node.value);
340                    drop(node);
341
342                    current = next;
343                }
344            }
345        }
346    }
347}
348
349#[cfg(test)]
350mod tests {
351    use super::*;
352    use std::sync::Arc;
353    use std::sync::atomic::AtomicUsize;
354
355    #[derive(Debug)]
356    struct DropCounter {
357        counter: Arc<AtomicUsize>,
358    }
359
360    impl DropCounter {
361        fn new(counter: Arc<AtomicUsize>) -> Self {
362            Self { counter }
363        }
364    }
365
366    impl Drop for DropCounter {
367        fn drop(&mut self) {
368            self.counter.fetch_add(1, Ordering::Relaxed);
369        }
370    }
371
372    #[test]
373    fn new_requires_power_of_two() {
374        let s = ConcurrentShardedStack::<usize>::with_concurrency(4);
375        assert_eq!(s.shard_count(), 4);
376    }
377
378    #[test]
379    #[should_panic]
380    fn new_panics_if_not_power_of_two() {
381        let _ = ConcurrentShardedStack::<usize>::with_concurrency(3);
382    }
383
384    #[test]
385    #[should_panic]
386    fn new_panics_if_too_many_shards() {
387        let _ = ConcurrentShardedStack::<usize>::with_concurrency((usize::BITS as usize) * 2);
388    }
389
390    #[test]
391    fn push_pop_single_thread() {
392        let s = ConcurrentShardedStack::with_concurrency(4);
393
394        s.push(1).unwrap();
395        s.push(2).unwrap();
396        s.push(3).unwrap();
397
398        assert_eq!(s.pop().unwrap(), 3);
399        assert_eq!(s.pop().unwrap(), 2);
400        assert_eq!(s.pop().unwrap(), 1);
401
402        assert_eq!(s.pop(), Err(PopError::Empty));
403    }
404
405    #[test]
406    fn close_works() {
407        let s = ConcurrentShardedStack::with_concurrency(4);
408
409        assert!(s.push(1).is_ok());
410
411        assert!(s.close());
412        assert!(!s.close());
413
414        assert_eq!(s.push(2), Err(PushError::Closed(2)));
415
416        assert_eq!(s.pop().unwrap(), 1);
417        assert_eq!(s.pop(), Err(PopError::Closed));
418    }
419
420    #[test]
421    fn multi_thread_push_pop() {
422        let s = Arc::new(ConcurrentShardedStack::with_concurrency(8));
423
424        let threads = 8;
425        // Miri executes far slower, so use a much smaller workload there.
426        #[cfg(miri)]
427        let per_thread = 200;
428        #[cfg(not(miri))]
429        let per_thread = 10_000;
430
431        let mut handles = Vec::new();
432
433        for t in 0..threads {
434            let s = Arc::clone(&s);
435
436            handles.push(std::thread::spawn(move || {
437                for i in 0..per_thread {
438                    s.push(t * per_thread + i).unwrap();
439                }
440            }));
441        }
442
443        for handle in handles {
444            handle.join().unwrap();
445        }
446
447        let mut handles = Vec::new();
448
449        for _ in 0..threads {
450            let s = Arc::clone(&s);
451
452            handles.push(std::thread::spawn(move || {
453                let mut count = 0usize;
454
455                loop {
456                    match s.pop() {
457                        Ok(_) => count += 1,
458                        Err(PopError::Empty) => break,
459                        Err(PopError::Closed) => break,
460                    }
461                }
462
463                count
464            }));
465        }
466
467        let total: usize = handles.into_iter().map(|h| h.join().unwrap()).sum();
468
469        assert_eq!(total, threads * per_thread);
470    }
471
472    #[test]
473    fn close_after_drain_returns_closed() {
474        let s = ConcurrentShardedStack::with_concurrency(4);
475
476        for i in 0..100 {
477            s.push(i).unwrap();
478        }
479
480        assert!(s.close());
481
482        let mut count = 0;
483
484        loop {
485            match s.pop() {
486                Ok(_) => count += 1,
487                Err(PopError::Empty) => continue,
488                Err(PopError::Closed) => break,
489            }
490        }
491
492        assert_eq!(count, 100);
493    }
494
495    #[test]
496    fn popped_values_are_dropped_exactly_once() {
497        let counter = Arc::new(AtomicUsize::new(0));
498        let s = ConcurrentShardedStack::with_concurrency(4);
499
500        for _ in 0..50 {
501            s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
502        }
503
504        // Pop everything; each popped value should be dropped exactly once when
505        // it goes out of scope here.
506        let mut popped = 0;
507        while let Ok(value) = s.pop() {
508            drop(value);
509            popped += 1;
510        }
511
512        assert_eq!(popped, 50);
513
514        // Force any deferred reclamation to run. Even after reclamation, the
515        // count must stay at exactly 50 (no double-drop from `defer_destroy`).
516        drop(s);
517        epoch::pin().flush();
518
519        assert_eq!(counter.load(Ordering::Relaxed), 50);
520    }
521
522    #[test]
523    fn remaining_values_are_dropped_when_stack_is_dropped() {
524        let counter = Arc::new(AtomicUsize::new(0));
525
526        {
527            let s = ConcurrentShardedStack::with_concurrency(4);
528            for _ in 0..30 {
529                s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
530            }
531            // Drop the stack without popping; all 30 values must be dropped once.
532        }
533
534        assert_eq!(counter.load(Ordering::Relaxed), 30);
535    }
536
537    #[test]
538    fn partially_drained_stack_drops_each_value_once() {
539        let counter = Arc::new(AtomicUsize::new(0));
540
541        {
542            let s = ConcurrentShardedStack::with_concurrency(4);
543            for _ in 0..40 {
544                s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
545            }
546
547            for _ in 0..15 {
548                let _ = s.pop().unwrap();
549            }
550            // 15 dropped via pop, 25 remain to be dropped by the stack's Drop.
551        }
552
553        epoch::pin().flush();
554        assert_eq!(counter.load(Ordering::Relaxed), 40);
555    }
556
557    #[test]
558    fn concurrent_drop_counter_no_double_free() {
559        let counter = Arc::new(AtomicUsize::new(0));
560        let s = Arc::new(ConcurrentShardedStack::with_concurrency(4));
561
562        let threads = 4;
563        #[cfg(miri)]
564        let per_thread = 50;
565        #[cfg(not(miri))]
566        let per_thread = 200;
567
568        let mut handles = Vec::new();
569        for _ in 0..threads {
570            let s = Arc::clone(&s);
571            let counter = Arc::clone(&counter);
572            handles.push(std::thread::spawn(move || {
573                for _ in 0..per_thread {
574                    s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
575                }
576            }));
577        }
578        for h in handles {
579            h.join().unwrap();
580        }
581
582        let mut handles = Vec::new();
583        for _ in 0..threads {
584            let s = Arc::clone(&s);
585            handles.push(std::thread::spawn(move || {
586                let mut popped = 0;
587                while let Ok(value) = s.pop() {
588                    drop(value);
589                    popped += 1;
590                }
591                popped
592            }));
593        }
594
595        let total: usize = handles.into_iter().map(|h| h.join().unwrap()).sum();
596        assert_eq!(total, threads * per_thread);
597
598        drop(s);
599        epoch::pin().flush();
600        assert_eq!(counter.load(Ordering::Relaxed), threads * per_thread);
601    }
602}