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;
#[cfg(feature = "intrusive")]
pub mod intrusive;
#[cfg(feature = "intrusive")]
pub use intrusive::{ConcurrentLinkOps, EpochAdapter, IntrusiveShardedStack, Retired};
#[cfg(feature = "intrusive")]
pub use intrusive_collections;
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 => {}
}
#[cfg(test)]
tests::after_empty_shard_scan();
}
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;
#[cfg(test)]
tests::after_shard_closed();
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();
let drain = || {
for shard in &self.shards {
loop {
let current = shard.load(Ordering::Relaxed, guard);
if current.is_null() {
break;
}
unsafe {
let mut node = Box::from_raw(current.as_raw() as *mut Node<T>);
let next = node.next.load(Ordering::Relaxed, guard);
shard.store(next, Ordering::Relaxed);
ManuallyDrop::drop(&mut node.value);
}
}
}
};
let cleanup = scopeguard::guard((), |_| drain());
drain();
scopeguard::ScopeGuard::into_inner(cleanup);
}
}
#[cfg(test)]
#[path = "tests/value.rs"]
mod tests;