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::{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 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
100pub struct ConcurrentShardedStack<T> {
102 shards: Box<[CachePadded<Atomic<Node<T>>>]>,
103
104 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 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 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 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 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 if let Some(value) = self.try_pop_from_shard(start, guard) {
219 return Ok(value);
220 }
221
222 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 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 pub fn close(&self) -> bool {
257 self.closed
258 .compare_exchange(false, true, Ordering::AcqRel, Ordering::Acquire)
259 .is_ok()
260 }
261
262 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 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 self.bitmap.fetch_and(!b, Ordering::AcqRel);
302 }
303
304 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 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 #[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 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 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 }
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 }
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}