concurrent_sharded_stack/
lib.rs1use 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 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 Empty,
81 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
116pub 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 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 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 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 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 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 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 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 let next = head_ref.next.load(Ordering::Relaxed, guard);
331
332 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 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 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;