use crate::signal::lock;
use std::{
collections::BTreeMap,
sync::{
Arc, Mutex,
atomic::{AtomicU64, AtomicUsize, Ordering},
},
};
#[path = "cancellation_graph.rs"]
mod graph;
#[path = "cancellation_subscription.rs"]
mod subscription;
use subscription::{FallbackWait, WaitSlot};
struct Domain {
epoch: Arc<AtomicU64>,
fallback_epoch: AtomicU64,
fallback_waits: Mutex<BTreeMap<usize, FallbackWait>>,
retired: Mutex<Vec<usize>>,
state: Mutex<State>,
}
const RETIREMENT_BATCH: usize = 64;
#[derive(Default)]
struct State {
graph: graph::Graph,
}
struct Node {
state: NodeState,
domain: Arc<Domain>,
wait: WaitSlot,
}
struct NodeState(AtomicUsize);
impl NodeState {
const CANCELLED: usize = 1 << (usize::BITS - 1);
fn new(id: usize) -> Self {
assert!(id < Self::CANCELLED, "cancellation identity exhausted");
Self(AtomicUsize::new(id))
}
#[inline]
fn id(&self) -> usize {
self.0.load(Ordering::Relaxed) & !Self::CANCELLED
}
#[inline]
fn cancel(&self) {
self.0.fetch_or(Self::CANCELLED, Ordering::SeqCst);
}
#[inline]
fn is_cancelled(&self) -> bool {
self.0.load(Ordering::SeqCst) & Self::CANCELLED != 0
}
}
impl Node {
#[inline]
fn id(&self) -> usize {
self.state.id()
}
}
impl Drop for Node {
fn drop(&mut self) {
let id = self.id();
lock(&self.domain.fallback_waits).remove(&id);
self.domain.retire(id);
}
}
impl Domain {
fn retire(self: &Arc<Self>, id: usize) {
let mut retired = lock(&self.retired);
retired.push(id);
if retired.len() < RETIREMENT_BATCH {
return;
}
let mut state = lock(&self.state);
for id in retired.drain(..) {
state.graph.remove(id);
}
}
#[cfg(test)]
fn flush_retired(&self) {
let mut retired = lock(&self.retired);
let mut state = lock(&self.state);
for id in retired.drain(..) {
state.graph.remove(id);
}
}
#[cfg(test)]
fn pending_retirements(&self) -> usize {
lock(&self.retired).len()
}
}
#[derive(Clone)]
pub struct CancellationToken(Arc<Node>);
impl CancellationToken {
pub(crate) fn root(capacity: usize) -> Self {
assert!(capacity != 0, "cancellation capacity must be positive");
let domain = Arc::new(Domain {
epoch: Arc::new(AtomicU64::new(1)),
fallback_epoch: AtomicU64::new(0),
fallback_waits: Mutex::default(),
retired: Mutex::new(Vec::with_capacity(RETIREMENT_BATCH)),
state: Mutex::default(),
});
Self::insert(&domain, &[])
}
fn insert(domain: &Arc<Domain>, parents: &[usize]) -> Self {
let mut state = lock(&domain.state);
let id = state.graph.reserve();
let node = Arc::new(Node {
state: NodeState::new(id),
domain: Arc::clone(domain),
wait: WaitSlot::new(),
});
let cancelled = state.graph.insert(id, parents, Arc::downgrade(&node));
if cancelled {
node.state.cancel();
}
drop(state);
Self(node)
}
pub fn child_token(&self) -> Self {
Self::insert(&self.0.domain, &[self.0.id()])
}
pub(crate) fn child_for_scope(&self, scope: &Self) -> Self {
assert!(Arc::ptr_eq(&self.0.domain, &scope.0.domain));
Self::insert(&self.0.domain, &[self.0.id(), scope.0.id()])
}
pub fn cancel(&self) {
let cancelled = {
let mut state = lock(&self.0.domain.state);
let cancelled = state.graph.cancel_nodes(self.0.id());
self.0.domain.epoch.fetch_add(1, Ordering::Release);
cancelled
};
let selected = cancelled
.into_iter()
.filter_map(|node| node.active_wait())
.collect::<Vec<_>>();
for (token, wait) in selected {
wait.select_cancelled(token);
}
}
#[inline]
pub fn is_cancelled(&self) -> bool {
self.0.state.is_cancelled()
}
pub(crate) fn into_cancellation_probe(self) -> (Self, Arc<AtomicU64>) {
let epoch = Arc::clone(&self.0.domain.epoch);
(self, epoch)
}
pub(crate) fn shares_epoch(&self, epoch: &Arc<AtomicU64>) -> bool {
Arc::ptr_eq(&self.0.domain.epoch, epoch)
}
#[cfg(test)]
fn graph_snapshot(&self) -> (usize, usize, usize) {
self.0.domain.flush_retired();
lock(&self.0.domain.state).graph.snapshot()
}
#[cfg(test)]
fn pending_retirements(&self) -> usize {
self.0.domain.pending_retirements()
}
}
impl std::fmt::Debug for CancellationToken {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("CancellationToken")
.field("cancelled", &self.is_cancelled())
.finish()
}
}
#[cfg(test)]
#[path = "cancellation_test.rs"]
mod cancellation_test;
#[cfg(test)]
#[path = "cancellation_history_test.rs"]
mod cancellation_history_test;
#[cfg(test)]
#[path = "cancellation_race_test.rs"]
mod cancellation_race_test;
#[cfg(test)]
#[path = "cancellation_dense_test.rs"]
mod cancellation_dense_test;