use crossbeam_epoch::{self as epoch, Atomic, Guard, Owned};
use crossbeam_utils::CachePadded;
use std::cell::Cell;
use std::fmt;
use std::hint::spin_loop;
use std::mem::ManuallyDrop;
use std::ptr;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::thread;
static NEXT_THREAD_ID: AtomicUsize = AtomicUsize::new(0);
const CLOSED_TAG: usize = 1;
thread_local! {
static THREAD_ID: Cell<usize> = Cell::new(
NEXT_THREAD_ID.fetch_add(1, Ordering::Relaxed)
);
}
fn current_thread_id() -> usize {
THREAD_ID.with(Cell::get)
}
#[derive(Debug, PartialEq, Eq)]
pub enum PushError<T> {
Closed(T),
}
impl<T> PushError<T> {
pub fn into_inner(self) -> T {
match self {
PushError::Closed(v) => v,
}
}
}
impl<T> fmt::Display for PushError<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
PushError::Closed(_) => write!(f, "stack is closed"),
}
}
}
impl<T: fmt::Debug> std::error::Error for PushError<T> {}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PopError {
Empty,
Closed,
}
impl fmt::Display for PopError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
PopError::Empty => write!(f, "stack is empty"),
PopError::Closed => write!(f, "stack is closed"),
}
}
}
impl std::error::Error for PopError {}
struct Node<T> {
value: ManuallyDrop<T>,
next: Atomic<Node<T>>,
}
impl<T> Node<T> {
fn new(value: T) -> Self {
Self {
value: ManuallyDrop::new(value),
next: Atomic::null(),
}
}
}
enum ShardPopResult<T> {
Popped(T),
Empty,
EmptyAndClosed,
}
pub struct ConcurrentShardedStack<T> {
shards: Box<[CachePadded<Atomic<Node<T>>>]>,
shard_index_mask: usize,
}
unsafe impl<T: Send> Send for ConcurrentShardedStack<T> {}
unsafe impl<T: Send> Sync for ConcurrentShardedStack<T> {}
impl<T> Default for ConcurrentShardedStack<T> {
fn default() -> Self {
Self::new()
}
}
impl<T> ConcurrentShardedStack<T> {
pub fn new() -> Self {
let concurrency = thread::available_parallelism()
.map(|n| n.get().next_power_of_two())
.unwrap_or(4);
Self::with_concurrency(concurrency)
}
pub fn with_concurrency(shard_count: usize) -> Self {
assert!(shard_count > 0, "shard_count must be non-zero");
assert!(
shard_count.is_power_of_two(),
"shard_count must be a power of two"
);
let mut shards = Vec::with_capacity(shard_count);
for _ in 0..shard_count {
shards.push(CachePadded::new(Atomic::null()));
}
Self {
shards: shards.into_boxed_slice(),
shard_index_mask: shard_count - 1,
}
}
pub fn push(&self, value: T) -> Result<(), PushError<T>> {
let shard_index = self.current_shard_index();
let shard = &self.shards[shard_index];
let guard = &epoch::pin();
let mut node = Owned::new(Node::new(value));
loop {
let head = shard.load(Ordering::Acquire, guard);
if head.tag() == CLOSED_TAG {
let node = node.into_box();
let value = unsafe { ptr::read(&*node.value) };
return Err(PushError::Closed(value));
}
node.next.store(head, Ordering::Relaxed);
match shard.compare_exchange_weak(
head,
node,
Ordering::Release,
Ordering::Relaxed,
guard,
) {
Ok(_) => return Ok(()),
Err(err) => {
node = err.new;
spin_loop();
}
}
}
}
pub fn pop(&self) -> Result<T, PopError> {
let guard = &epoch::pin();
let start = self.current_shard_index();
let shard_count = self.shards.len();
let mut all_closed = true;
for mask in 0..shard_count {
let index = start ^ mask;
match self.pop_one(index, guard) {
ShardPopResult::Popped(value) => return Ok(value),
ShardPopResult::Empty => {
all_closed = false;
}
ShardPopResult::EmptyAndClosed => {}
}
}
if all_closed {
Err(PopError::Closed)
} else {
Err(PopError::Empty)
}
}
pub fn close(&self) -> bool {
let guard = &epoch::pin();
let mut changed = false;
for shard in self.shards.iter() {
loop {
let head = shard.load(Ordering::Acquire, guard);
if head.tag() == CLOSED_TAG {
break;
}
match shard.compare_exchange_weak(
head,
head.with_tag(CLOSED_TAG),
Ordering::AcqRel,
Ordering::Relaxed,
guard,
) {
Ok(_) => {
changed = true;
break;
}
Err(_) => spin_loop(),
}
}
}
changed
}
pub fn is_closed(&self) -> bool {
let guard = &epoch::pin();
self.all_shards_closed(guard)
}
pub fn shard_count(&self) -> usize {
self.shards.len()
}
fn current_shard_index(&self) -> usize {
current_thread_id() & self.shard_index_mask
}
fn pop_one(&self, index: usize, guard: &Guard) -> ShardPopResult<T> {
let shard = &self.shards[index];
loop {
let head = shard.load(Ordering::Acquire, guard);
let closed = head.tag() == CLOSED_TAG;
if head.is_null() {
return if closed {
ShardPopResult::EmptyAndClosed
} else {
ShardPopResult::Empty
};
}
let head_ref = unsafe { head.deref() };
let next = head_ref.next.load(Ordering::Relaxed, guard);
let new_head = next.with_tag(head.tag());
match shard.compare_exchange(head, new_head, Ordering::AcqRel, Ordering::Relaxed, guard)
{
Ok(_) => {
let value = unsafe { ptr::read(&*head_ref.value) };
unsafe {
guard.defer_destroy(head.with_tag(0));
}
return ShardPopResult::Popped(value);
}
Err(_) => {
spin_loop();
}
}
}
}
fn all_shards_closed(&self, guard: &Guard) -> bool {
self.shards
.iter()
.all(|shard| shard.load(Ordering::Acquire, guard).tag() == CLOSED_TAG)
}
}
impl<T> Drop for ConcurrentShardedStack<T> {
fn drop(&mut self) {
let guard = &epoch::pin();
for shard in self.shards.iter() {
let mut current = shard.load(Ordering::Relaxed, guard);
while !current.is_null() {
unsafe {
let raw = current.as_raw() as *mut Node<T>;
let next = (*raw).next.load(Ordering::Relaxed, guard);
let mut node = Box::from_raw(raw);
ManuallyDrop::drop(&mut node.value);
drop(node);
current = next;
}
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, AtomicUsize};
use std::time::{Duration, Instant};
#[derive(Debug)]
struct DropCounter {
counter: Arc<AtomicUsize>,
}
impl DropCounter {
fn new(counter: Arc<AtomicUsize>) -> Self {
Self { counter }
}
}
impl Drop for DropCounter {
fn drop(&mut self) {
self.counter.fetch_add(1, Ordering::Relaxed);
}
}
#[test]
fn new_requires_power_of_two() {
let s = ConcurrentShardedStack::<usize>::with_concurrency(4);
assert_eq!(s.shard_count(), 4);
}
#[test]
#[should_panic]
fn new_panics_if_not_power_of_two() {
let _ = ConcurrentShardedStack::<usize>::with_concurrency(3);
}
#[test]
fn push_pop_single_thread() {
let s = ConcurrentShardedStack::with_concurrency(4);
s.push(1).unwrap();
s.push(2).unwrap();
s.push(3).unwrap();
assert_eq!(s.pop().unwrap(), 3);
assert_eq!(s.pop().unwrap(), 2);
assert_eq!(s.pop().unwrap(), 1);
assert_eq!(s.pop(), Err(PopError::Empty));
}
#[test]
fn close_works() {
let s = ConcurrentShardedStack::with_concurrency(4);
assert!(s.push(1).is_ok());
assert!(s.close());
assert!(!s.close());
assert_eq!(s.push(2), Err(PushError::Closed(2)));
assert_eq!(s.pop().unwrap(), 1);
assert_eq!(s.pop(), Err(PopError::Closed));
}
#[test]
fn multi_thread_push_pop() {
let s = Arc::new(ConcurrentShardedStack::with_concurrency(8));
let threads = 8;
#[cfg(miri)]
let per_thread = 200;
#[cfg(not(miri))]
let per_thread = 10_000;
let mut handles = Vec::new();
for t in 0..threads {
let s = Arc::clone(&s);
handles.push(std::thread::spawn(move || {
for i in 0..per_thread {
s.push(t * per_thread + i).unwrap();
}
}));
}
for handle in handles {
handle.join().unwrap();
}
let mut handles = Vec::new();
for _ in 0..threads {
let s = Arc::clone(&s);
handles.push(std::thread::spawn(move || {
let mut count = 0usize;
loop {
match s.pop() {
Ok(_) => count += 1,
Err(PopError::Empty) => break,
Err(PopError::Closed) => break,
}
}
count
}));
}
let total: usize = handles.into_iter().map(|h| h.join().unwrap()).sum();
assert_eq!(total, threads * per_thread);
}
#[test]
fn close_after_drain_returns_closed() {
let s = ConcurrentShardedStack::with_concurrency(4);
for i in 0..100 {
s.push(i).unwrap();
}
assert!(s.close());
let mut count = 0;
loop {
match s.pop() {
Ok(_) => count += 1,
Err(PopError::Empty) => continue,
Err(PopError::Closed) => break,
}
}
assert_eq!(count, 100);
}
#[test]
fn popped_values_are_dropped_exactly_once() {
let counter = Arc::new(AtomicUsize::new(0));
let s = ConcurrentShardedStack::with_concurrency(4);
for _ in 0..50 {
s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
}
let mut popped = 0;
while let Ok(value) = s.pop() {
drop(value);
popped += 1;
}
assert_eq!(popped, 50);
drop(s);
epoch::pin().flush();
assert_eq!(counter.load(Ordering::Relaxed), 50);
}
#[test]
fn remaining_values_are_dropped_when_stack_is_dropped() {
let counter = Arc::new(AtomicUsize::new(0));
{
let s = ConcurrentShardedStack::with_concurrency(4);
for _ in 0..30 {
s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
}
}
assert_eq!(counter.load(Ordering::Relaxed), 30);
}
#[test]
fn partially_drained_stack_drops_each_value_once() {
let counter = Arc::new(AtomicUsize::new(0));
{
let s = ConcurrentShardedStack::with_concurrency(4);
for _ in 0..40 {
s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
}
for _ in 0..15 {
let _ = s.pop().unwrap();
}
}
epoch::pin().flush();
assert_eq!(counter.load(Ordering::Relaxed), 40);
}
#[test]
fn concurrent_drop_counter_no_double_free() {
let counter = Arc::new(AtomicUsize::new(0));
let s = Arc::new(ConcurrentShardedStack::with_concurrency(4));
let threads = 4;
#[cfg(miri)]
let per_thread = 50;
#[cfg(not(miri))]
let per_thread = 200;
let mut handles = Vec::new();
for _ in 0..threads {
let s = Arc::clone(&s);
let counter = Arc::clone(&counter);
handles.push(std::thread::spawn(move || {
for _ in 0..per_thread {
s.push(DropCounter::new(Arc::clone(&counter))).unwrap();
}
}));
}
for h in handles {
h.join().unwrap();
}
let mut handles = Vec::new();
for _ in 0..threads {
let s = Arc::clone(&s);
handles.push(std::thread::spawn(move || {
let mut popped = 0;
while let Ok(value) = s.pop() {
drop(value);
popped += 1;
}
popped
}));
}
let total: usize = handles.into_iter().map(|h| h.join().unwrap()).sum();
assert_eq!(total, threads * per_thread);
drop(s);
epoch::pin().flush();
assert_eq!(counter.load(Ordering::Relaxed), threads * per_thread);
}
fn wait_until<F: Fn() -> bool>(timeout: Duration, label: &str, cond: F) {
let start = Instant::now();
while !cond() {
if start.elapsed() > timeout {
panic!("{label}: condition not met within {timeout:?}");
}
std::thread::sleep(Duration::from_millis(5));
}
}
#[cfg_attr(miri, ignore)]
#[test]
fn no_element_loss_open_asymmetric() {
#[cfg(miri)]
let (n_pushers, n_poppers, per_pusher, rounds) = (2, 2, 200, 1);
#[cfg(not(miri))]
let (n_pushers, n_poppers, per_pusher, rounds) = (4, 12, 50_000, 4);
for round in 0..rounds {
let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(16));
let popped = Arc::new(AtomicUsize::new(0));
let pushed = Arc::new(AtomicUsize::new(0));
let stop = Arc::new(AtomicBool::new(false));
let total = n_pushers * per_pusher;
let mut handles = Vec::new();
for t in 0..n_pushers {
let s = Arc::clone(&s);
let pushed = Arc::clone(&pushed);
handles.push(std::thread::spawn(move || {
for i in 0..per_pusher {
s.push(t * per_pusher + i).unwrap();
pushed.fetch_add(1, Ordering::Relaxed);
}
}));
}
for _ in 0..n_poppers {
let s = Arc::clone(&s);
let popped = Arc::clone(&popped);
let stop = Arc::clone(&stop);
handles.push(std::thread::spawn(move || {
while !stop.load(Ordering::Relaxed) {
match s.pop() {
Ok(_) => {
popped.fetch_add(1, Ordering::Relaxed);
}
Err(PopError::Empty) => std::hint::spin_loop(),
Err(PopError::Closed) => break,
}
}
}));
}
wait_until(Duration::from_secs(30), "popper drain (open)", || {
popped.load(Ordering::Relaxed) >= total
});
stop.store(true, Ordering::Relaxed);
for h in handles {
h.join().unwrap();
}
let final_pushed = pushed.load(Ordering::Relaxed);
let final_popped = popped.load(Ordering::Relaxed);
assert_eq!(
final_popped, final_pushed,
"round {round}: popped {final_popped} != pushed {final_pushed}",
);
}
}
#[test]
fn no_element_loss_after_close_asymmetric() {
#[cfg(miri)]
let (n_pushers, n_poppers, per_pusher, rounds) = (2, 2, 200, 1);
#[cfg(not(miri))]
let (n_pushers, n_poppers, per_pusher, rounds) = (4, 12, 50_000, 4);
for round in 0..rounds {
let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(16));
let popped = Arc::new(AtomicUsize::new(0));
let total = n_pushers * per_pusher;
let mut handles = Vec::new();
for t in 0..n_pushers {
let s = Arc::clone(&s);
handles.push(std::thread::spawn(move || {
for i in 0..per_pusher {
s.push(t * per_pusher + i).unwrap();
}
}));
}
for _ in 0..n_poppers {
let s = Arc::clone(&s);
let popped = Arc::clone(&popped);
handles.push(std::thread::spawn(move || {
loop {
match s.pop() {
Ok(_) => {
popped.fetch_add(1, Ordering::Relaxed);
}
Err(PopError::Empty) => std::hint::spin_loop(),
Err(PopError::Closed) => break,
}
}
}));
}
let pusher_handles: Vec<_> = handles.drain(..n_pushers).collect();
for h in pusher_handles {
h.join().unwrap();
}
s.close();
for h in handles {
h.join().unwrap();
}
assert_eq!(
popped.load(Ordering::Relaxed),
total,
"round {round}: drain after close lost elements",
);
}
}
#[test]
fn no_element_loss_few_threads_many_shards() {
#[cfg(miri)]
let (n_pushers, n_poppers, per_pusher, shards) = (2, 1, 100, 8);
#[cfg(not(miri))]
let (n_pushers, n_poppers, per_pusher, shards) = (2, 1, 100_000, 32);
let s = Arc::new(ConcurrentShardedStack::<usize>::with_concurrency(shards));
let popped = Arc::new(AtomicUsize::new(0));
let total = n_pushers * per_pusher;
let mut handles = Vec::new();
for _ in 0..n_pushers {
let s = Arc::clone(&s);
handles.push(std::thread::spawn(move || {
for i in 0..per_pusher {
s.push(i).unwrap();
}
}));
}
for _ in 0..n_poppers {
let s = Arc::clone(&s);
let popped = Arc::clone(&popped);
handles.push(std::thread::spawn(move || {
let start = Instant::now();
while popped.load(Ordering::Relaxed) < total {
match s.pop() {
Ok(_) => {
popped.fetch_add(1, Ordering::Relaxed);
}
Err(PopError::Empty) => std::hint::spin_loop(),
Err(PopError::Closed) => break,
}
if start.elapsed() > Duration::from_secs(30) {
panic!(
"popper stuck: popped {} of {}",
popped.load(Ordering::Relaxed),
total,
);
}
}
}));
}
for h in handles {
h.join().unwrap();
}
assert_eq!(popped.load(Ordering::Relaxed), total);
}
}