Skip to main content

concurrent_sharded_stack/
lib.rs

1//! Sharded concurrent stacks for unordered object recycling.
2//!
3//! [`ConcurrentShardedStack`] uses a lock-free Treiber stack and epoch GC.
4//! With the default `intrusive` feature, `IntrusiveShardedStack` uses embedded
5//! links and returns retired nodes for reuse after an epoch grace period.
6//! Both provide LIFO ordering within a shard, without global ordering.
7//!
8//! # Example
9//!
10//! ```
11//! use concurrent_sharded_stack::{ConcurrentShardedStack, PopError};
12//!
13//! let stack = ConcurrentShardedStack::with_concurrency(4);
14//! stack.push(1).unwrap();
15//! stack.push(2).unwrap();
16//!
17//! assert_eq!(stack.pop().unwrap(), 2);
18//! assert_eq!(stack.pop().unwrap(), 1);
19//! assert_eq!(stack.pop(), Err(PopError::Empty));
20//! ```
21
22use crossbeam_epoch::{self as epoch, Atomic, Guard, Owned};
23use crossbeam_utils::CachePadded;
24use std::cell::Cell;
25use std::fmt;
26use std::hint::spin_loop;
27use std::mem::ManuallyDrop;
28use std::ptr;
29use std::sync::atomic::{AtomicUsize, Ordering};
30use std::thread;
31
32#[cfg(feature = "intrusive")]
33pub mod intrusive;
34#[cfg(feature = "intrusive")]
35pub use intrusive::{ConcurrentLinkOps, EpochAdapter, IntrusiveShardedStack, Retired};
36#[cfg(feature = "intrusive")]
37pub use intrusive_collections;
38
39static NEXT_THREAD_ID: AtomicUsize = AtomicUsize::new(0);
40
41const CLOSED_TAG: usize = 1;
42
43thread_local! {
44    static THREAD_ID: Cell<usize> = Cell::new(
45        NEXT_THREAD_ID.fetch_add(1, Ordering::Relaxed)
46    );
47}
48
49fn current_thread_id() -> usize {
50    THREAD_ID.with(Cell::get)
51}
52
53#[derive(Debug, PartialEq, Eq)]
54pub enum PushError<T> {
55    /// The target shard has been closed.
56    Closed(T),
57}
58
59impl<T> PushError<T> {
60    pub fn into_inner(self) -> T {
61        match self {
62            PushError::Closed(v) => v,
63        }
64    }
65}
66
67impl<T> fmt::Display for PushError<T> {
68    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
69        match self {
70            PushError::Closed(_) => write!(f, "stack is closed"),
71        }
72    }
73}
74
75impl<T: fmt::Debug> std::error::Error for PushError<T> {}
76
77#[derive(Debug, Clone, Copy, PartialEq, Eq)]
78pub enum PopError {
79    /// No item was found by this scan; concurrent activity may hide items.
80    Empty,
81    /// Every shard was observed closed and empty; no later push can succeed.
82    Closed,
83}
84
85impl fmt::Display for PopError {
86    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
87        match self {
88            PopError::Empty => write!(f, "stack is empty"),
89            PopError::Closed => write!(f, "stack is closed"),
90        }
91    }
92}
93
94impl std::error::Error for PopError {}
95
96struct Node<T> {
97    value: ManuallyDrop<T>,
98    next: Atomic<Node<T>>,
99}
100
101impl<T> Node<T> {
102    fn new(value: T) -> Self {
103        Self {
104            value: ManuallyDrop::new(value),
105            next: Atomic::null(),
106        }
107    }
108}
109
110enum ShardPopResult<T> {
111    Popped(T),
112    Empty,
113    EmptyAndClosed,
114}
115
116/// Concurrent sharded Treiber stack.
117///
118/// Ordering is LIFO within each shard, not across shards. An unsuccessful
119/// [`pop`](Self::pop) is a scan, not an atomic snapshot: `Empty` can be returned
120/// even when the stack remained nonempty throughout the call. Closing also
121/// takes effect one shard at a time; see [`close`](Self::close).
122pub struct ConcurrentShardedStack<T> {
123    shards: Box<[CachePadded<Atomic<Node<T>>>]>,
124    shard_index_mask: usize,
125}
126
127unsafe impl<T: Send> Send for ConcurrentShardedStack<T> {}
128unsafe impl<T: Send> Sync for ConcurrentShardedStack<T> {}
129
130impl<T> Default for ConcurrentShardedStack<T> {
131    fn default() -> Self {
132        Self::new()
133    }
134}
135
136impl<T> ConcurrentShardedStack<T> {
137    /// Creates a stack using `available_parallelism()` as concurrency hint.
138    pub fn new() -> Self {
139        let concurrency = thread::available_parallelism()
140            .map(|n| n.get().next_power_of_two())
141            .unwrap_or(4);
142
143        Self::with_concurrency(concurrency)
144    }
145
146    /// Creates a stack with exact shard count.
147    ///
148    /// Panics if:
149    ///
150    /// - `shard_count == 0`
151    /// - `shard_count` is not power of two
152    pub fn with_concurrency(shard_count: usize) -> Self {
153        assert!(shard_count > 0, "shard_count must be non-zero");
154
155        assert!(
156            shard_count.is_power_of_two(),
157            "shard_count must be a power of two"
158        );
159
160        let mut shards = Vec::with_capacity(shard_count);
161
162        for _ in 0..shard_count {
163            shards.push(CachePadded::new(Atomic::null()));
164        }
165
166        Self {
167            shards: shards.into_boxed_slice(),
168            shard_index_mask: shard_count - 1,
169        }
170    }
171
172    /// Pushes a value into the stack.
173    ///
174    /// Returns `Err(PushError::Closed(value))` if this thread's shard is closed.
175    /// While [`close`](Self::close) is in progress, some shards may reject
176    /// pushes while others still accept them. After `close` returns, every
177    /// shard rejects pushes.
178    pub fn push(&self, value: T) -> Result<(), PushError<T>> {
179        let shard_index = self.current_shard_index();
180        let shard = &self.shards[shard_index];
181
182        let guard = &epoch::pin();
183        let mut node = Owned::new(Node::new(value));
184
185        loop {
186            let head = shard.load(Ordering::Acquire, guard);
187
188            if head.tag() == CLOSED_TAG {
189                let node = node.into_box();
190                let value = unsafe { ptr::read(&*node.value) };
191                return Err(PushError::Closed(value));
192            }
193
194            node.next.store(head, Ordering::Relaxed);
195
196            match shard.compare_exchange_weak(
197                head,
198                node,
199                Ordering::Release,
200                Ordering::Relaxed,
201                guard,
202            ) {
203                Ok(_) => return Ok(()),
204                Err(err) => {
205                    node = err.new;
206                    spin_loop();
207                }
208            }
209        }
210    }
211
212    /// Pops a value from the stack non-blocking.
213    ///
214    /// Scans the local shard first, then `start ^ 1`, `start ^ 2`, and so on.
215    ///
216    /// Returns `Err(PopError::Empty)` if no element is found and at least one
217    /// shard is still observed open. This is not a consistent snapshot: other
218    /// threads can push into an already-scanned shard and drain a later shard,
219    /// so `Empty` can occur even if the stack was never globally empty during
220    /// the call. Consumers with active producers should retry rather than use
221    /// `Empty` as a completion signal.
222    ///
223    /// Returns `Err(PopError::Closed)` if no element is found and every shard
224    /// is observed closed. Unlike `Empty`, this is terminal: closed shards
225    /// cannot receive more elements.
226    pub fn pop(&self) -> Result<T, PopError> {
227        let guard = &epoch::pin();
228        let start = self.current_shard_index();
229        let shard_count = self.shards.len();
230
231        let mut all_closed = true;
232
233        for mask in 0..shard_count {
234            let index = start ^ mask;
235
236            match self.pop_one(index, guard) {
237                ShardPopResult::Popped(value) => return Ok(value),
238                ShardPopResult::Empty => {
239                    all_closed = false;
240                }
241                ShardPopResult::EmptyAndClosed => {}
242            }
243            #[cfg(test)]
244            tests::after_empty_shard_scan();
245        }
246
247        if all_closed {
248            Err(PopError::Closed)
249        } else {
250            Err(PopError::Empty)
251        }
252    }
253
254    /// Closes every shard. Existing elements can still be popped.
255    ///
256    /// Closure propagates one shard at a time. During the call, a push can be
257    /// rejected on one shard while a later push succeeds on another, and
258    /// [`is_closed`](Self::is_closed) can still return `false` after a rejected
259    /// push. Once this method returns, all shards are closed.
260    ///
261    /// Returns `true` if this call closed at least one shard. Concurrent calls
262    /// can both return `true`; the result does not identify a unique closer.
263    pub fn close(&self) -> bool {
264        let guard = &epoch::pin();
265        let mut changed = false;
266
267        for shard in self.shards.iter() {
268            loop {
269                let head = shard.load(Ordering::Acquire, guard);
270
271                if head.tag() == CLOSED_TAG {
272                    break;
273                }
274
275                match shard.compare_exchange_weak(
276                    head,
277                    head.with_tag(CLOSED_TAG),
278                    Ordering::AcqRel,
279                    Ordering::Relaxed,
280                    guard,
281                ) {
282                    Ok(_) => {
283                        changed = true;
284                        #[cfg(test)]
285                        tests::after_shard_closed();
286                        break;
287                    }
288                    Err(_) => spin_loop(),
289                }
290            }
291        }
292
293        changed
294    }
295
296    /// Checks whether every shard is closed.
297    pub fn is_closed(&self) -> bool {
298        let guard = &epoch::pin();
299        self.all_shards_closed(guard)
300    }
301
302    pub fn shard_count(&self) -> usize {
303        self.shards.len()
304    }
305
306    fn current_shard_index(&self) -> usize {
307        current_thread_id() & self.shard_index_mask
308    }
309
310    /// Retries CAS until this shard yields a value or is observed empty.
311    fn pop_one(&self, index: usize, guard: &Guard) -> ShardPopResult<T> {
312        let shard = &self.shards[index];
313
314        loop {
315            let head = shard.load(Ordering::Acquire, guard);
316            let closed = head.tag() == CLOSED_TAG;
317
318            if head.is_null() {
319                return if closed {
320                    ShardPopResult::EmptyAndClosed
321                } else {
322                    ShardPopResult::Empty
323                };
324            }
325
326            let head_ref = unsafe { head.deref() };
327
328            // `head` was published by a Release CAS that we synchronized with
329            // via the Acquire load above, so the node's fields are visible.
330            let next = head_ref.next.load(Ordering::Relaxed, guard);
331
332            // Preserve the CLOSED tag when popping from a closed shard.
333            let new_head = next.with_tag(head.tag());
334
335            match shard.compare_exchange(head, new_head, Ordering::AcqRel, Ordering::Relaxed, guard)
336            {
337                Ok(_) => {
338                    // Move the value out of the popped node. The node itself
339                    // is reclaimed later by epoch GC; because `value` is inside
340                    // `ManuallyDrop<T>`, deferred destruction will not drop it again.
341                    let value = unsafe { ptr::read(&*head_ref.value) };
342
343                    unsafe {
344                        guard.defer_destroy(head.with_tag(0));
345                    }
346
347                    return ShardPopResult::Popped(value);
348                }
349                Err(_) => {
350                    spin_loop();
351                }
352            }
353        }
354    }
355
356    fn all_shards_closed(&self, guard: &Guard) -> bool {
357        self.shards
358            .iter()
359            .all(|shard| shard.load(Ordering::Acquire, guard).tag() == CLOSED_TAG)
360    }
361}
362
363impl<T> Drop for ConcurrentShardedStack<T> {
364    fn drop(&mut self) {
365        let guard = &epoch::pin();
366        let drain = || {
367            for shard in &self.shards {
368                loop {
369                    let current = shard.load(Ordering::Relaxed, guard);
370                    if current.is_null() {
371                        break;
372                    }
373
374                    // SAFETY: dropping the stack requires exclusive access,
375                    // so no operation can still access its reachable nodes.
376                    // Advance the head before user code so a panic leaves only
377                    // the remaining nodes reachable for the cleanup guard.
378                    unsafe {
379                        let mut node = Box::from_raw(current.as_raw() as *mut Node<T>);
380                        let next = node.next.load(Ordering::Relaxed, guard);
381                        shard.store(next, Ordering::Relaxed);
382                        ManuallyDrop::drop(&mut node.value);
383                    }
384                }
385            }
386        };
387
388        let cleanup = scopeguard::guard((), |_| drain());
389        drain();
390        scopeguard::ScopeGuard::into_inner(cleanup);
391    }
392}
393
394#[cfg(test)]
395#[path = "tests/value.rs"]
396mod tests;