#[cfg(loom)]
use loom::sync::atomic::{AtomicU64, Ordering};
#[cfg(loom)]
use loom::sync::{Arc, Mutex};
use std::collections::HashMap;
use std::hash::{BuildHasher, Hash, RandomState};
use std::num::{NonZeroU64, NonZeroUsize};
#[cfg(not(loom))]
use std::sync::atomic::{AtomicU64, Ordering};
#[cfg(not(loom))]
use std::sync::{Arc, Mutex};
use crate::{
ActivationId, DispatchId, DrainFailure, EntityId, LifecycleMachine, LifecycleOutput, Refusal,
RetirementMode, SlotEffect, SlotEffectBatch, SlotEvent, TransitionEvidence, lifecycle_machine,
};
use bombay_machine_executor::{LinearizedExecutor, OutputEvidence};
use bombay_transition::Machine;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct DirectoryConfig {
pub shards: NonZeroUsize,
pub activation_waiters: NonZeroUsize,
}
impl Default for DirectoryConfig {
fn default() -> Self {
Self {
shards: NonZeroUsize::new(64).expect("64 is non-zero"),
activation_waiters: NonZeroUsize::new(64).expect("64 is non-zero"),
}
}
}
#[derive(Debug, thiserror::Error)]
pub enum DirectoryError<C> {
#[error("shard count was not a power of two")]
InvalidShardCount,
#[error("activation identity namespace is exhausted")]
ActivationIdsExhausted(C),
#[error("dispatch identity namespace is exhausted")]
DispatchIdsExhausted(C),
}
pub trait EffectInterpreter<I, C, E, L> {
fn start_activation(&self, entity_id: EntityId<I>, activation_id: ActivationId);
fn deliver(
&self,
entity_id: EntityId<I>,
activation_id: ActivationId,
dispatch_id: DispatchId,
endpoint: E,
command: C,
);
fn reject(&self, dispatch_id: DispatchId, command: C, reason: Refusal);
fn enqueue_fence(&self, entity_id: EntityId<I>, activation_id: ActivationId, endpoint: E);
fn retire(
&self,
entity_id: EntityId<I>,
activation_id: ActivationId,
lease: L,
retirement: RetirementMode,
);
}
#[must_use = "installed lifecycle decision awaits effect interpretation via LocalDirectory::interpret"]
pub struct DirectoryOutput<I, C, E, L> {
pub evidence: TransitionEvidence,
pub(crate) activation_id: Option<ActivationId>,
entity_id: EntityId<I>,
target: OutputTarget<C, E, L>,
}
enum OutputTarget<C, E, L> {
Mapped(Arc<Slot<C, E, L>>),
Transient(Box<SlotEffectBatch<C, E, L>>),
}
#[must_use = "installed lifecycle decision awaits effect interpretation via LocalDirectory::interpret"]
pub struct DispatchOutput<I, C, E, L> {
pub dispatch_id: DispatchId,
pub output: DirectoryOutput<I, C, E, L>,
}
struct Slot<C, E, L> {
lifecycle: LinearizedExecutor<LifecycleMachine<C, E, L>>,
}
struct Installed {
evidence: TransitionEvidence,
activation_id: Option<ActivationId>,
}
impl<C, E: Clone, L> Slot<C, E, L> {
fn new() -> Self {
Self {
lifecycle: LinearizedExecutor::new(lifecycle_machine()),
}
}
fn submit(&self, event: SlotEvent<C, E, L>) -> Installed {
let (evidence, activation_id) = self.lifecycle.submit(event);
Installed {
evidence,
activation_id,
}
}
fn activation_id(&self) -> Option<ActivationId> {
self.lifecycle.evidence().and_then(|evidence| evidence.1)
}
}
type Shard<I, C, E, L> = Mutex<HashMap<EntityId<I>, Arc<Slot<C, E, L>>>>;
pub struct LocalDirectory<I, C, E, L, S = RandomState> {
shards: Box<[Shard<I, C, E, L>]>,
mask: u64,
hash_builder: S,
waiter_limit: NonZeroUsize,
next_activation: AtomicU64,
next_dispatch: AtomicU64,
}
impl<I, C, E, L> LocalDirectory<I, C, E, L>
where
I: Eq + Hash + Clone,
E: Clone,
{
pub fn new(config: DirectoryConfig) -> Result<Self, DirectoryError<C>> {
Self::with_hasher(config, RandomState::new())
}
}
impl<I, C, E, L, S> LocalDirectory<I, C, E, L, S>
where
I: Eq + Hash + Clone,
E: Clone,
S: BuildHasher,
{
pub fn with_hasher(
config: DirectoryConfig,
hash_builder: S,
) -> Result<Self, DirectoryError<C>> {
if !config.shards.get().is_power_of_two() {
return Err(DirectoryError::InvalidShardCount);
}
let mask = config
.shards
.get()
.checked_sub(1)
.and_then(|count| u64::try_from(count).ok())
.ok_or(DirectoryError::InvalidShardCount)?;
let shards = (0..config.shards.get())
.map(|_| Mutex::new(HashMap::new()))
.collect();
Ok(Self {
shards,
mask,
hash_builder,
waiter_limit: config.activation_waiters,
next_activation: AtomicU64::new(1),
next_dispatch: AtomicU64::new(1),
})
}
pub fn dispatch(
&self,
entity_id: EntityId<I>,
command: C,
) -> Result<DispatchOutput<I, C, E, L>, DirectoryError<C>> {
let Some(dispatch_sequence) = allocate(&self.next_dispatch) else {
return Err(DirectoryError::DispatchIdsExhausted(command));
};
let dispatch_id = DispatchId::new(dispatch_sequence);
let shard = &self.shards[self.shard_index(&entity_id)];
let mut entries = shard.lock().expect("directory shard lock poisoned");
if let Some(slot) = entries.get(&entity_id) {
let slot = Arc::clone(slot);
drop(entries);
let installed = slot.submit(SlotEvent::Dispatch {
dispatch_id,
command,
});
return Ok(DispatchOutput {
dispatch_id,
output: directory_output(
entity_id,
installed.evidence,
installed.activation_id,
OutputTarget::Mapped(slot),
),
});
}
let Some(activation_sequence) = allocate(&self.next_activation) else {
return Err(DirectoryError::ActivationIdsExhausted(command));
};
let activation_id = ActivationId::new(activation_sequence);
let slot = Arc::new(Slot::new());
let installed = slot.submit(SlotEvent::ClaimActivation {
activation_id,
dispatch_id,
command,
waiter_limit: self.waiter_limit,
});
entries.insert(entity_id.clone(), Arc::clone(&slot));
drop(entries);
Ok(DispatchOutput {
dispatch_id,
output: directory_output(
entity_id,
installed.evidence,
installed.activation_id,
OutputTarget::Mapped(slot),
),
})
}
pub fn activation_succeeded(
&self,
entity_id: &EntityId<I>,
activation_id: ActivationId,
endpoint: E,
lease: L,
) -> DirectoryOutput<I, C, E, L> {
let event = SlotEvent::ActivationSucceeded {
activation_id,
endpoint,
lease,
};
self.submit_or_inactive(entity_id, event)
}
pub fn activation_failed(
&self,
entity_id: &EntityId<I>,
activation_id: ActivationId,
) -> DirectoryOutput<I, C, E, L> {
self.submit_or_inactive(entity_id, SlotEvent::ActivationFailed { activation_id })
}
pub fn cancel_waiter(
&self,
entity_id: &EntityId<I>,
activation_id: ActivationId,
dispatch_id: DispatchId,
) -> DirectoryOutput<I, C, E, L> {
self.submit_or_inactive(
entity_id,
SlotEvent::CancelWaiter {
activation_id,
dispatch_id,
},
)
}
pub fn delivery_resolved(
&self,
entity_id: &EntityId<I>,
activation_id: ActivationId,
failure: Option<(DispatchId, C)>,
) -> DirectoryOutput<I, C, E, L> {
self.submit_or_inactive(
entity_id,
SlotEvent::DeliveryResolved {
activation_id,
failure,
},
)
}
pub fn begin_drain(
&self,
entity_id: &EntityId<I>,
activation_id: ActivationId,
) -> DirectoryOutput<I, C, E, L> {
self.submit_or_inactive(entity_id, SlotEvent::BeginDrain { activation_id })
}
pub fn fence_acknowledged(
&self,
entity_id: &EntityId<I>,
activation_id: ActivationId,
) -> DirectoryOutput<I, C, E, L> {
self.submit_or_inactive(entity_id, SlotEvent::FenceAcknowledged { activation_id })
}
pub fn force_drain(
&self,
entity_id: &EntityId<I>,
activation_id: ActivationId,
failure: DrainFailure,
) -> DirectoryOutput<I, C, E, L> {
self.submit_or_inactive(
entity_id,
SlotEvent::ForceDrain {
activation_id,
failure,
},
)
}
pub fn terminated(
&self,
entity_id: &EntityId<I>,
activation_id: ActivationId,
) -> DirectoryOutput<I, C, E, L> {
self.submit_or_inactive(entity_id, SlotEvent::Terminated { activation_id })
}
#[must_use]
pub fn len(&self) -> usize {
self.shards
.iter()
.map(|shard| shard.lock().expect("directory shard lock poisoned").len())
.sum()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub(crate) fn current_activation(&self, entity_id: &EntityId<I>) -> Option<ActivationId> {
self.shards[self.shard_index(entity_id)]
.lock()
.expect("directory shard lock poisoned")
.get(entity_id)
.cloned()
.and_then(|slot| slot.activation_id())
}
fn submit_or_inactive(
&self,
entity_id: &EntityId<I>,
event: SlotEvent<C, E, L>,
) -> DirectoryOutput<I, C, E, L> {
let slot = self.shards[self.shard_index(entity_id)]
.lock()
.expect("directory shard lock poisoned")
.get(entity_id)
.cloned();
if let Some(slot) = slot {
let installed = slot.submit(event);
return directory_output(
entity_id.clone(),
installed.evidence,
installed.activation_id,
OutputTarget::Mapped(slot),
);
}
submit_absent(entity_id.clone(), event)
}
pub fn interpret<R>(&self, output: DirectoryOutput<I, C, E, L>, runtime: &R)
where
R: EffectInterpreter<I, C, E, L>,
{
let DirectoryOutput {
entity_id, target, ..
} = output;
match target {
OutputTarget::Mapped(slot) => {
slot.lifecycle
.dispatch_pending(&|output: LifecycleOutput<C, E, L>| {
output.effects.for_each(|effect| {
self.apply_effect(&entity_id, Some(&slot), effect, runtime);
});
});
}
OutputTarget::Transient(effects) => {
effects.for_each(|effect| self.apply_effect(&entity_id, None, effect, runtime));
}
}
}
#[inline]
fn apply_effect<R>(
&self,
entity_id: &EntityId<I>,
slot: Option<&Arc<Slot<C, E, L>>>,
effect: SlotEffect<C, E, L>,
runtime: &R,
) where
R: EffectInterpreter<I, C, E, L>,
{
match effect {
SlotEffect::StartActivation { activation_id } => {
runtime.start_activation(entity_id.clone(), activation_id);
}
SlotEffect::Deliver {
activation_id,
dispatch_id,
endpoint,
command,
} => runtime.deliver(
entity_id.clone(),
activation_id,
dispatch_id,
endpoint,
command,
),
SlotEffect::Reject {
dispatch_id,
command,
reason,
} => runtime.reject(dispatch_id, command, reason),
SlotEffect::EnqueueFence {
activation_id,
endpoint,
} => runtime.enqueue_fence(entity_id.clone(), activation_id, endpoint),
SlotEffect::Retire {
activation_id,
lease,
retirement,
} => runtime.retire(entity_id.clone(), activation_id, lease, retirement),
SlotEffect::Remove { .. } => {
if let Some(slot) = slot {
self.remove_matching(entity_id, slot);
}
}
}
}
fn remove_matching(&self, entity_id: &EntityId<I>, slot: &Arc<Slot<C, E, L>>) {
let mut entries = self.shards[self.shard_index(entity_id)]
.lock()
.expect("directory shard lock poisoned");
if entries
.get(entity_id)
.is_some_and(|stored| Arc::ptr_eq(stored, slot))
{
entries.remove(entity_id);
}
}
fn shard_index(&self, entity_id: &EntityId<I>) -> usize {
usize::try_from(self.hash_builder.hash_one(entity_id) & self.mask)
.expect("masked hash fits usize")
}
}
impl<C, E, L> OutputEvidence for LifecycleOutput<C, E, L> {
type Evidence = (TransitionEvidence, Option<ActivationId>);
fn evidence(&self) -> Self::Evidence {
(self.evidence, self.activation_id)
}
}
fn allocate(sequence: &AtomicU64) -> Option<NonZeroU64> {
sequence
.fetch_update(Ordering::Relaxed, Ordering::Relaxed, |current| {
current.checked_add(1)
})
.ok()
.and_then(NonZeroU64::new)
}
#[cold]
#[inline(never)]
fn submit_absent<I, C, E: Clone, L>(
entity_id: EntityId<I>,
event: SlotEvent<C, E, L>,
) -> DirectoryOutput<I, C, E, L> {
let (output, _) = lifecycle_machine().step(event);
directory_output(
entity_id,
output.evidence,
output.activation_id,
OutputTarget::Transient(Box::new(output.effects)),
)
}
fn directory_output<I, C, E, L>(
entity_id: EntityId<I>,
evidence: TransitionEvidence,
activation_id: Option<ActivationId>,
target: OutputTarget<C, E, L>,
) -> DirectoryOutput<I, C, E, L> {
DirectoryOutput {
evidence,
activation_id,
entity_id,
target,
}
}