Skip to main content

bombay_entity/
directory.rs

1//! Concurrent storage for local entity lifecycle machines.
2
3#[cfg(loom)]
4use loom::sync::atomic::{AtomicU64, Ordering};
5#[cfg(loom)]
6use loom::sync::{Arc, Mutex};
7use std::collections::HashMap;
8use std::hash::{BuildHasher, Hash, RandomState};
9use std::num::{NonZeroU64, NonZeroUsize};
10#[cfg(not(loom))]
11use std::sync::atomic::{AtomicU64, Ordering};
12#[cfg(not(loom))]
13use std::sync::{Arc, Mutex};
14
15use crate::{
16    ActivationId, DispatchId, DrainFailure, EntityId, LifecycleMachine, LifecycleOutput, Refusal,
17    RetirementMode, SlotEffect, SlotEffectBatch, SlotEvent, TransitionEvidence, lifecycle_machine,
18};
19use bombay_machine_executor::{LinearizedExecutor, OutputEvidence};
20use bombay_transition::Machine;
21
22/// Fixed sizing and admission limits for a local directory.
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub struct DirectoryConfig {
25    /// Number of independently locked map shards; must be a power of two.
26    pub shards: NonZeroUsize,
27    /// Maximum commands retained by one in-flight activation.
28    pub activation_waiters: NonZeroUsize,
29}
30
31impl Default for DirectoryConfig {
32    fn default() -> Self {
33        Self {
34            shards: NonZeroUsize::new(64).expect("64 is non-zero"),
35            activation_waiters: NonZeroUsize::new(64).expect("64 is non-zero"),
36        }
37    }
38}
39
40/// Failure before a command can be submitted to a lifecycle machine.
41#[derive(Debug, thiserror::Error)]
42pub enum DirectoryError<C> {
43    /// The shard count was not a power of two.
44    #[error("shard count was not a power of two")]
45    InvalidShardCount,
46    /// The monotonically increasing activation namespace is exhausted.
47    #[error("activation identity namespace is exhausted")]
48    ActivationIdsExhausted(C),
49    /// The monotonically increasing dispatch namespace is exhausted.
50    #[error("dispatch identity namespace is exhausted")]
51    DispatchIdsExhausted(C),
52}
53
54/// Runtime capabilities used to interpret lifecycle effects.
55///
56/// Methods run without directory or slot synchronization held. Asynchronous
57/// implementations should schedule owned work and later submit its typed fact
58/// through the directory. Calls for one slot occur in declared effect order.
59pub trait EffectInterpreter<I, C, E, L> {
60    /// Start one directory-owned activation attempt.
61    fn start_activation(&self, entity_id: EntityId<I>, activation_id: ActivationId);
62    /// Start delivery to one exact-incarnation endpoint.
63    fn deliver(
64        &self,
65        entity_id: EntityId<I>,
66        activation_id: ActivationId,
67        dispatch_id: DispatchId,
68        endpoint: E,
69        command: C,
70    );
71    /// Return a command that was not admitted or delivered.
72    fn reject(&self, dispatch_id: DispatchId, command: C, reason: Refusal);
73    /// Enqueue an ordered processing fence for one exact incarnation.
74    fn enqueue_fence(&self, entity_id: EntityId<I>, activation_id: ActivationId, endpoint: E);
75    /// Exercise exact-incarnation retirement authority.
76    fn retire(
77        &self,
78        entity_id: EntityId<I>,
79        activation_id: ActivationId,
80        lease: L,
81        retirement: RetirementMode,
82    );
83}
84
85/// One installed lifecycle decision awaiting effect interpretation.
86#[must_use = "installed lifecycle decision awaits effect interpretation via LocalDirectory::interpret"]
87pub struct DirectoryOutput<I, C, E, L> {
88    /// Checked evidence for the installed lifecycle decision.
89    pub evidence: TransitionEvidence,
90    pub(crate) activation_id: Option<ActivationId>,
91    entity_id: EntityId<I>,
92    target: OutputTarget<C, E, L>,
93}
94
95/// Where an installed decision's effects await interpretation.
96enum OutputTarget<C, E, L> {
97    /// A directory-mapped slot with queued effects.
98    Mapped(Arc<Slot<C, E, L>>),
99    /// Effects already resolved for an event addressed to an absent entry.
100    /// Boxed: the cold variant stays off the mapped output's move path
101    /// (measured: inline costs the active dispatch path ~8%).
102    Transient(Box<SlotEffectBatch<C, E, L>>),
103}
104
105/// The installed decision for one dispatched command, with its guaranteed
106/// correlation identity.
107#[must_use = "installed lifecycle decision awaits effect interpretation via LocalDirectory::interpret"]
108pub struct DispatchOutput<I, C, E, L> {
109    /// Correlation identity allocated for the dispatched command.
110    pub dispatch_id: DispatchId,
111    /// Installed decision awaiting effect interpretation.
112    pub output: DirectoryOutput<I, C, E, L>,
113}
114
115struct Slot<C, E, L> {
116    lifecycle: LinearizedExecutor<LifecycleMachine<C, E, L>>,
117}
118
119struct Installed {
120    evidence: TransitionEvidence,
121    activation_id: Option<ActivationId>,
122}
123
124impl<C, E: Clone, L> Slot<C, E, L> {
125    fn new() -> Self {
126        Self {
127            lifecycle: LinearizedExecutor::new(lifecycle_machine()),
128        }
129    }
130
131    fn submit(&self, event: SlotEvent<C, E, L>) -> Installed {
132        let (evidence, activation_id) = self.lifecycle.submit(event);
133        Installed {
134            evidence,
135            activation_id,
136        }
137    }
138
139    fn activation_id(&self) -> Option<ActivationId> {
140        self.lifecycle.evidence().and_then(|evidence| evidence.1)
141    }
142}
143
144type Shard<I, C, E, L> = Mutex<HashMap<EntityId<I>, Arc<Slot<C, E, L>>>>;
145
146/// Sharded local storage for authoritative per-entity lifecycle machines.
147///
148/// Hashing first selects a shard before locking; [`Hash`] and [`Eq`] for `I`
149/// then run during table operations while that shard lock is held and therefore
150/// must not reenter this directory. Lifecycle effect callbacks run only after
151/// directory synchronization is released.
152pub struct LocalDirectory<I, C, E, L, S = RandomState> {
153    shards: Box<[Shard<I, C, E, L>]>,
154    mask: u64,
155    hash_builder: S,
156    waiter_limit: NonZeroUsize,
157    next_activation: AtomicU64,
158    next_dispatch: AtomicU64,
159}
160
161impl<I, C, E, L> LocalDirectory<I, C, E, L>
162where
163    I: Eq + Hash + Clone,
164    E: Clone,
165{
166    /// Construct a directory using the standard randomized hash builder.
167    ///
168    /// # Errors
169    ///
170    /// Returns [`DirectoryError::InvalidShardCount`] unless the configured
171    /// shard count is a power of two.
172    pub fn new(config: DirectoryConfig) -> Result<Self, DirectoryError<C>> {
173        Self::with_hasher(config, RandomState::new())
174    }
175}
176
177impl<I, C, E, L, S> LocalDirectory<I, C, E, L, S>
178where
179    I: Eq + Hash + Clone,
180    E: Clone,
181    S: BuildHasher,
182{
183    /// Construct a directory with an explicit hash builder.
184    ///
185    /// # Errors
186    ///
187    /// Returns [`DirectoryError::InvalidShardCount`] unless the configured
188    /// shard count is a power of two.
189    pub fn with_hasher(
190        config: DirectoryConfig,
191        hash_builder: S,
192    ) -> Result<Self, DirectoryError<C>> {
193        if !config.shards.get().is_power_of_two() {
194            return Err(DirectoryError::InvalidShardCount);
195        }
196        let mask = config
197            .shards
198            .get()
199            .checked_sub(1)
200            .and_then(|count| u64::try_from(count).ok())
201            .ok_or(DirectoryError::InvalidShardCount)?;
202        let shards = (0..config.shards.get())
203            .map(|_| Mutex::new(HashMap::new()))
204            .collect();
205        Ok(Self {
206            shards,
207            mask,
208            hash_builder,
209            waiter_limit: config.activation_waiters,
210            next_activation: AtomicU64::new(1),
211            next_dispatch: AtomicU64::new(1),
212        })
213    }
214
215    /// Dispatch a command through the stable slot for `entity_id`.
216    ///
217    /// The first caller atomically installs an activating machine. Concurrent
218    /// callers use that same slot and bounded activation attempt.
219    ///
220    /// # Errors
221    ///
222    /// Returns the original command if either identity namespace is exhausted.
223    ///
224    /// # Panics
225    ///
226    /// Panics after a synchronization poison, which cannot be recovered without
227    /// risking lifecycle corruption.
228    pub fn dispatch(
229        &self,
230        entity_id: EntityId<I>,
231        command: C,
232    ) -> Result<DispatchOutput<I, C, E, L>, DirectoryError<C>> {
233        let Some(dispatch_sequence) = allocate(&self.next_dispatch) else {
234            return Err(DirectoryError::DispatchIdsExhausted(command));
235        };
236        let dispatch_id = DispatchId::new(dispatch_sequence);
237        let shard = &self.shards[self.shard_index(&entity_id)];
238        let mut entries = shard.lock().expect("directory shard lock poisoned");
239        if let Some(slot) = entries.get(&entity_id) {
240            let slot = Arc::clone(slot);
241            drop(entries);
242            let installed = slot.submit(SlotEvent::Dispatch {
243                dispatch_id,
244                command,
245            });
246            return Ok(DispatchOutput {
247                dispatch_id,
248                output: directory_output(
249                    entity_id,
250                    installed.evidence,
251                    installed.activation_id,
252                    OutputTarget::Mapped(slot),
253                ),
254            });
255        }
256        let Some(activation_sequence) = allocate(&self.next_activation) else {
257            return Err(DirectoryError::ActivationIdsExhausted(command));
258        };
259        let activation_id = ActivationId::new(activation_sequence);
260        let slot = Arc::new(Slot::new());
261        let installed = slot.submit(SlotEvent::ClaimActivation {
262            activation_id,
263            dispatch_id,
264            command,
265            waiter_limit: self.waiter_limit,
266        });
267        entries.insert(entity_id.clone(), Arc::clone(&slot));
268        drop(entries);
269        Ok(DispatchOutput {
270            dispatch_id,
271            output: directory_output(
272                entity_id,
273                installed.evidence,
274                installed.activation_id,
275                OutputTarget::Mapped(slot),
276            ),
277        })
278    }
279
280    /// Submit successful exact-incarnation activation to the represented slot.
281    pub fn activation_succeeded(
282        &self,
283        entity_id: &EntityId<I>,
284        activation_id: ActivationId,
285        endpoint: E,
286        lease: L,
287    ) -> DirectoryOutput<I, C, E, L> {
288        let event = SlotEvent::ActivationSucceeded {
289            activation_id,
290            endpoint,
291            lease,
292        };
293        self.submit_or_inactive(entity_id, event)
294    }
295
296    /// Submit a failed activation attempt to the represented slot.
297    pub fn activation_failed(
298        &self,
299        entity_id: &EntityId<I>,
300        activation_id: ActivationId,
301    ) -> DirectoryOutput<I, C, E, L> {
302        self.submit_or_inactive(entity_id, SlotEvent::ActivationFailed { activation_id })
303    }
304
305    /// Cancel one bounded activation waiter.
306    pub fn cancel_waiter(
307        &self,
308        entity_id: &EntityId<I>,
309        activation_id: ActivationId,
310        dispatch_id: DispatchId,
311    ) -> DirectoryOutput<I, C, E, L> {
312        self.submit_or_inactive(
313            entity_id,
314            SlotEvent::CancelWaiter {
315                activation_id,
316                dispatch_id,
317            },
318        )
319    }
320
321    /// Resolve one previously admitted exact-incarnation delivery.
322    pub fn delivery_resolved(
323        &self,
324        entity_id: &EntityId<I>,
325        activation_id: ActivationId,
326        failure: Option<(DispatchId, C)>,
327    ) -> DirectoryOutput<I, C, E, L> {
328        self.submit_or_inactive(
329            entity_id,
330            SlotEvent::DeliveryResolved {
331                activation_id,
332                failure,
333            },
334        )
335    }
336
337    /// Atomically close admission for an exact active incarnation.
338    pub fn begin_drain(
339        &self,
340        entity_id: &EntityId<I>,
341        activation_id: ActivationId,
342    ) -> DirectoryOutput<I, C, E, L> {
343        self.submit_or_inactive(entity_id, SlotEvent::BeginDrain { activation_id })
344    }
345
346    /// Submit acknowledgement of the ordered processing fence.
347    pub fn fence_acknowledged(
348        &self,
349        entity_id: &EntityId<I>,
350        activation_id: ActivationId,
351    ) -> DirectoryOutput<I, C, E, L> {
352        self.submit_or_inactive(entity_id, SlotEvent::FenceAcknowledged { activation_id })
353    }
354
355    /// Force a bounded drain to retirement with its exact failure stage.
356    pub fn force_drain(
357        &self,
358        entity_id: &EntityId<I>,
359        activation_id: ActivationId,
360        failure: DrainFailure,
361    ) -> DirectoryOutput<I, C, E, L> {
362        self.submit_or_inactive(
363            entity_id,
364            SlotEvent::ForceDrain {
365                activation_id,
366                failure,
367            },
368        )
369    }
370
371    /// Submit an exact-incarnation termination observation.
372    pub fn terminated(
373        &self,
374        entity_id: &EntityId<I>,
375        activation_id: ActivationId,
376    ) -> DirectoryOutput<I, C, E, L> {
377        self.submit_or_inactive(entity_id, SlotEvent::Terminated { activation_id })
378    }
379
380    /// Return the number of represented stable routing slots.
381    ///
382    /// # Panics
383    ///
384    /// Panics if a directory shard lock was poisoned.
385    #[must_use]
386    pub fn len(&self) -> usize {
387        // The sum cannot overflow: every counted entry is a live heap
388        // allocation, so the total is bounded far below usize::MAX.
389        self.shards
390            .iter()
391            .map(|shard| shard.lock().expect("directory shard lock poisoned").len())
392            .sum()
393    }
394
395    /// Return whether no stable routing slots are represented.
396    #[must_use]
397    pub fn is_empty(&self) -> bool {
398        self.len() == 0
399    }
400
401    pub(crate) fn current_activation(&self, entity_id: &EntityId<I>) -> Option<ActivationId> {
402        self.shards[self.shard_index(entity_id)]
403            .lock()
404            .expect("directory shard lock poisoned")
405            .get(entity_id)
406            .cloned()
407            .and_then(|slot| slot.activation_id())
408    }
409
410    fn submit_or_inactive(
411        &self,
412        entity_id: &EntityId<I>,
413        event: SlotEvent<C, E, L>,
414    ) -> DirectoryOutput<I, C, E, L> {
415        let slot = self.shards[self.shard_index(entity_id)]
416            .lock()
417            .expect("directory shard lock poisoned")
418            .get(entity_id)
419            .cloned();
420        if let Some(slot) = slot {
421            let installed = slot.submit(event);
422            return directory_output(
423                entity_id.clone(),
424                installed.evidence,
425                installed.activation_id,
426                OutputTarget::Mapped(slot),
427            );
428        }
429        // No entry: reduce the event on a stack-resident machine instead of
430        // allocating a slot that would be discarded after interpretation.
431        submit_absent(entity_id.clone(), event)
432    }
433
434    /// Interpret all effects queued for the output's stable slot.
435    ///
436    /// A concurrent or reentrant call only contributes its already-queued
437    /// effects; the current interpreter retains ownership until the queue is
438    /// empty. Runtime callbacks execute without directory synchronization held.
439    pub fn interpret<R>(&self, output: DirectoryOutput<I, C, E, L>, runtime: &R)
440    where
441        R: EffectInterpreter<I, C, E, L>,
442    {
443        let DirectoryOutput {
444            entity_id, target, ..
445        } = output;
446        match target {
447            OutputTarget::Mapped(slot) => {
448                slot.lifecycle
449                    .dispatch_pending(&|output: LifecycleOutput<C, E, L>| {
450                        output.effects.for_each(|effect| {
451                            self.apply_effect(&entity_id, Some(&slot), effect, runtime);
452                        });
453                    });
454            }
455            OutputTarget::Transient(effects) => {
456                effects.for_each(|effect| self.apply_effect(&entity_id, None, effect, runtime));
457            }
458        }
459    }
460
461    #[inline]
462    fn apply_effect<R>(
463        &self,
464        entity_id: &EntityId<I>,
465        slot: Option<&Arc<Slot<C, E, L>>>,
466        effect: SlotEffect<C, E, L>,
467        runtime: &R,
468    ) where
469        R: EffectInterpreter<I, C, E, L>,
470    {
471        match effect {
472            SlotEffect::StartActivation { activation_id } => {
473                runtime.start_activation(entity_id.clone(), activation_id);
474            }
475            SlotEffect::Deliver {
476                activation_id,
477                dispatch_id,
478                endpoint,
479                command,
480            } => runtime.deliver(
481                entity_id.clone(),
482                activation_id,
483                dispatch_id,
484                endpoint,
485                command,
486            ),
487            SlotEffect::Reject {
488                dispatch_id,
489                command,
490                reason,
491            } => runtime.reject(dispatch_id, command, reason),
492            SlotEffect::EnqueueFence {
493                activation_id,
494                endpoint,
495            } => runtime.enqueue_fence(entity_id.clone(), activation_id, endpoint),
496            SlotEffect::Retire {
497                activation_id,
498                lease,
499                retirement,
500            } => runtime.retire(entity_id.clone(), activation_id, lease, retirement),
501            // A mapped slot never acquires a second activation, so pointer
502            // identity is the exact removal authority. A transient decision
503            // belongs to no mapped slot, so its Remove cannot match anything.
504            SlotEffect::Remove { .. } => {
505                if let Some(slot) = slot {
506                    self.remove_matching(entity_id, slot);
507                }
508            }
509        }
510    }
511
512    fn remove_matching(&self, entity_id: &EntityId<I>, slot: &Arc<Slot<C, E, L>>) {
513        let mut entries = self.shards[self.shard_index(entity_id)]
514            .lock()
515            .expect("directory shard lock poisoned");
516        if entries
517            .get(entity_id)
518            .is_some_and(|stored| Arc::ptr_eq(stored, slot))
519        {
520            entries.remove(entity_id);
521        }
522    }
523
524    fn shard_index(&self, entity_id: &EntityId<I>) -> usize {
525        // The mask derives from the shard count, so the masked hash always
526        // fits the pointer width that allocated the shards.
527        usize::try_from(self.hash_builder.hash_one(entity_id) & self.mask)
528            .expect("masked hash fits usize")
529    }
530}
531
532impl<C, E, L> OutputEvidence for LifecycleOutput<C, E, L> {
533    type Evidence = (TransitionEvidence, Option<ActivationId>);
534
535    fn evidence(&self) -> Self::Evidence {
536        (self.evidence, self.activation_id)
537    }
538}
539
540/// Allocate the next non-zero identity from a monotonic sequence.
541///
542/// `Relaxed` suffices by structural argument: the only requirement is
543/// uniqueness, which the atomic read-modify-write modification order already
544/// guarantees for any ordering. No non-atomic state is published through these
545/// counters — every identity is an opaque token, and all slot state it later
546/// names is synchronized by the shard and executor mutexes instead.
547fn allocate(sequence: &AtomicU64) -> Option<NonZeroU64> {
548    sequence
549        .fetch_update(Ordering::Relaxed, Ordering::Relaxed, |current| {
550            current.checked_add(1)
551        })
552        .ok()
553        .and_then(NonZeroU64::new)
554}
555
556/// Reduce an event addressed to an absent entry on a stack-resident machine.
557#[cold]
558#[inline(never)]
559fn submit_absent<I, C, E: Clone, L>(
560    entity_id: EntityId<I>,
561    event: SlotEvent<C, E, L>,
562) -> DirectoryOutput<I, C, E, L> {
563    let (output, _) = lifecycle_machine().step(event);
564    directory_output(
565        entity_id,
566        output.evidence,
567        output.activation_id,
568        OutputTarget::Transient(Box::new(output.effects)),
569    )
570}
571
572fn directory_output<I, C, E, L>(
573    entity_id: EntityId<I>,
574    evidence: TransitionEvidence,
575    activation_id: Option<ActivationId>,
576    target: OutputTarget<C, E, L>,
577) -> DirectoryOutput<I, C, E, L> {
578    DirectoryOutput {
579        evidence,
580        activation_id,
581        entity_id,
582        target,
583    }
584}