use crate::{CLOSED_TAG, PopError, PushError, current_thread_id};
use crossbeam_epoch::{self as epoch, Atomic, Shared};
use crossbeam_utils::CachePadded;
use intrusive_collections::singly_linked_list::{AtomicLinkOps, SinglyLinkedListOps};
use intrusive_collections::{Adapter, LinkOps, PointerOps, SinglyLinkedListAtomicLink};
use std::ptr::NonNull;
use std::sync::atomic::Ordering;
type Pointer<A> = <<A as Adapter>::PointerOps as PointerOps>::Pointer;
type Link<A> = <<A as Adapter>::LinkOps as ConcurrentLinkOps>::Link;
pub unsafe trait ConcurrentLinkOps:
LinkOps<LinkPtr = NonNull<Self::Link>> + Send + Sync
{
type Link: Send + Sync + 'static;
unsafe fn try_acquire(&self, link: NonNull<Self::Link>) -> bool;
unsafe fn release(&self, link: NonNull<Self::Link>);
unsafe fn load_next(&self, link: NonNull<Self::Link>) -> Option<NonNull<Self::Link>>;
unsafe fn store_next(&self, link: NonNull<Self::Link>, next: Option<NonNull<Self::Link>>);
}
unsafe impl ConcurrentLinkOps for AtomicLinkOps {
type Link = SinglyLinkedListAtomicLink;
unsafe fn try_acquire(&self, link: NonNull<Self::Link>) -> bool {
let mut ops = *self;
unsafe { LinkOps::acquire_link(&mut ops, link) }
}
unsafe fn release(&self, link: NonNull<Self::Link>) {
let mut ops = *self;
unsafe { LinkOps::release_link(&mut ops, link) }
}
unsafe fn load_next(&self, link: NonNull<Self::Link>) -> Option<NonNull<Self::Link>> {
unsafe { SinglyLinkedListOps::next(self, link) }
}
unsafe fn store_next(&self, link: NonNull<Self::Link>, next: Option<NonNull<Self::Link>>) {
let mut ops = *self;
unsafe { SinglyLinkedListOps::set_next(&mut ops, link, next) }
}
}
pub unsafe trait EpochAdapter: Adapter + Clone + Send + Sync + 'static {}
pub struct Retired<A: EpochAdapter>
where
A::LinkOps: ConcurrentLinkOps,
Pointer<A>: Send + 'static,
{
link: Option<NonNull<Link<A>>>,
adapter: A,
}
unsafe impl<A: EpochAdapter> Send for Retired<A>
where
A::LinkOps: ConcurrentLinkOps,
Pointer<A>: Send + 'static,
{
}
impl<A: EpochAdapter> Retired<A>
where
A::LinkOps: ConcurrentLinkOps,
Pointer<A>: Send + 'static,
{
pub fn defer(self, callback: impl FnOnce(Pointer<A>) + Send + 'static) {
let guard = epoch::pin();
guard.defer(move || callback(unsafe { self.reclaim() }));
}
unsafe fn reclaim(mut self) -> Pointer<A> {
let link = self.link.take().expect("retired node already consumed");
unsafe {
let value = self.adapter.get_value(link);
self.adapter.link_ops().release(link);
self.adapter.pointer_ops().from_raw(value)
}
}
}
impl<A: EpochAdapter> Drop for Retired<A>
where
A::LinkOps: ConcurrentLinkOps,
Pointer<A>: Send + 'static,
{
fn drop(&mut self) {
if let Some(link) = self.link.take() {
Self {
link: Some(link),
adapter: self.adapter.clone(),
}
.defer(drop);
}
}
}
pub fn collect() {
epoch::pin().flush();
}
pub struct IntrusiveShardedStack<A: EpochAdapter>
where
A::LinkOps: ConcurrentLinkOps,
Pointer<A>: Send + 'static,
{
shards: Box<[CachePadded<Atomic<Link<A>>>]>,
adapter: A,
}
impl<A: EpochAdapter> IntrusiveShardedStack<A>
where
A::LinkOps: ConcurrentLinkOps,
Pointer<A>: Send + 'static,
{
pub fn new(adapter: A) -> Self {
let count = std::thread::available_parallelism()
.map(|n| n.get().next_power_of_two())
.unwrap_or(4);
Self::with_concurrency(count, adapter)
}
pub fn with_concurrency(shard_count: usize, adapter: A) -> Self {
assert!(
shard_count.is_power_of_two(),
"shard_count must be a nonzero power of two"
);
assert!(
std::mem::align_of::<Link<A>>() >= 2,
"link alignment must leave a close tag bit"
);
Self {
shards: (0..shard_count)
.map(|_| CachePadded::new(Atomic::null()))
.collect(),
adapter,
}
}
pub fn push(&self, value: Pointer<A>) -> Result<(), PushError<Pointer<A>>> {
let guard = &epoch::pin();
let shard = &self.shards[self.current_shard_index()];
if shard.load(Ordering::Acquire, guard).tag() == CLOSED_TAG {
return Err(PushError::Closed(value));
}
let raw = self.adapter.pointer_ops().into_raw(value);
let link = unsafe { self.adapter.get_link(raw) };
if !unsafe { self.adapter.link_ops().try_acquire(link) } {
drop(unsafe { self.adapter.pointer_ops().from_raw(raw) });
panic!("attempted to insert an object that is already linked or retired");
}
let node = Shared::from(link.as_ptr() as *const Link<A>);
loop {
let head = shard.load(Ordering::Acquire, guard);
if head.tag() == CLOSED_TAG {
unsafe {
self.adapter.link_ops().release(link);
}
return Err(PushError::Closed(unsafe {
self.adapter.pointer_ops().from_raw(raw)
}));
}
unsafe {
self.adapter
.link_ops()
.store_next(link, NonNull::new(head.as_raw() as *mut Link<A>));
}
if shard
.compare_exchange_weak(head, node, Ordering::Release, Ordering::Relaxed, guard)
.is_ok()
{
return Ok(());
}
std::hint::spin_loop();
}
}
pub fn pop(&self) -> Result<Retired<A>, PopError> {
let adapter = self.adapter.clone();
let guard = &epoch::pin();
let mut all_closed = true;
for mask in 0..self.shards.len() {
let shard = &self.shards[self.current_shard_index() ^ mask];
loop {
let head = shard.load(Ordering::Acquire, guard);
let Some(link) = NonNull::new(head.as_raw() as *mut Link<A>) else {
all_closed &= head.tag() == CLOSED_TAG;
break;
};
let next = unsafe { adapter.link_ops().load_next(link) };
let next = next
.map_or(Shared::null(), |p| {
Shared::from(p.as_ptr() as *const Link<A>)
})
.with_tag(head.tag());
if shard
.compare_exchange(head, next, Ordering::AcqRel, Ordering::Relaxed, guard)
.is_ok()
{
return Ok(Retired {
link: Some(link),
adapter,
});
}
std::hint::spin_loop();
}
}
Err(if all_closed {
PopError::Closed
} else {
PopError::Empty
})
}
pub fn close(&self) -> bool {
let guard = &epoch::pin();
let mut changed = false;
for shard in &self.shards {
loop {
let head = shard.load(Ordering::Acquire, guard);
if head.tag() == CLOSED_TAG {
break;
}
if shard
.compare_exchange_weak(
head,
head.with_tag(CLOSED_TAG),
Ordering::AcqRel,
Ordering::Relaxed,
guard,
)
.is_ok()
{
changed = true;
break;
}
std::hint::spin_loop();
}
}
changed
}
pub fn is_closed(&self) -> bool {
let guard = &epoch::pin();
self.shards
.iter()
.all(|s| s.load(Ordering::Acquire, guard).tag() == CLOSED_TAG)
}
pub fn shard_count(&self) -> usize {
self.shards.len()
}
fn current_shard_index(&self) -> usize {
current_thread_id() & (self.shards.len() - 1)
}
}
impl<A: EpochAdapter + Default> Default for IntrusiveShardedStack<A>
where
A::LinkOps: ConcurrentLinkOps,
Pointer<A>: Send + 'static,
{
fn default() -> Self {
Self::new(A::default())
}
}
impl<A: EpochAdapter> Drop for IntrusiveShardedStack<A>
where
A::LinkOps: ConcurrentLinkOps,
Pointer<A>: Send + 'static,
{
fn drop(&mut self) {
let drain = || {
let guard = unsafe { epoch::unprotected() };
for shard in &self.shards {
loop {
let head = shard.load(Ordering::Relaxed, guard);
let Some(link) = NonNull::new(head.as_raw() as *mut Link<A>) else {
break;
};
unsafe {
let next = self.adapter.link_ops().load_next(link);
shard.store(
next.map_or(Shared::null(), |p| {
Shared::from(p.as_ptr() as *const Link<A>)
}),
Ordering::Relaxed,
);
drop(
Retired {
link: Some(link),
adapter: self.adapter.clone(),
}
.reclaim(),
);
}
}
}
};
let cleanup = scopeguard::guard((), |_| drain());
drain();
scopeguard::ScopeGuard::into_inner(cleanup);
}
}