1#[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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub struct DirectoryConfig {
25 pub shards: NonZeroUsize,
27 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#[derive(Debug, thiserror::Error)]
42pub enum DirectoryError<C> {
43 #[error("shard count was not a power of two")]
45 InvalidShardCount,
46 #[error("activation identity namespace is exhausted")]
48 ActivationIdsExhausted(C),
49 #[error("dispatch identity namespace is exhausted")]
51 DispatchIdsExhausted(C),
52}
53
54pub trait EffectInterpreter<I, C, E, L> {
60 fn start_activation(&self, entity_id: EntityId<I>, activation_id: ActivationId);
62 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 fn reject(&self, dispatch_id: DispatchId, command: C, reason: Refusal);
73 fn enqueue_fence(&self, entity_id: EntityId<I>, activation_id: ActivationId, endpoint: E);
75 fn retire(
77 &self,
78 entity_id: EntityId<I>,
79 activation_id: ActivationId,
80 lease: L,
81 retirement: RetirementMode,
82 );
83}
84
85#[must_use = "installed lifecycle decision awaits effect interpretation via LocalDirectory::interpret"]
87pub struct DirectoryOutput<I, C, E, L> {
88 pub evidence: TransitionEvidence,
90 pub(crate) activation_id: Option<ActivationId>,
91 entity_id: EntityId<I>,
92 target: OutputTarget<C, E, L>,
93}
94
95enum OutputTarget<C, E, L> {
97 Mapped(Arc<Slot<C, E, L>>),
99 Transient(Box<SlotEffectBatch<C, E, L>>),
103}
104
105#[must_use = "installed lifecycle decision awaits effect interpretation via LocalDirectory::interpret"]
108pub struct DispatchOutput<I, C, E, L> {
109 pub dispatch_id: DispatchId,
111 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
146pub 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 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 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 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 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 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 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 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 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 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 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 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 #[must_use]
386 pub fn len(&self) -> usize {
387 self.shards
390 .iter()
391 .map(|shard| shard.lock().expect("directory shard lock poisoned").len())
392 .sum()
393 }
394
395 #[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 submit_absent(entity_id.clone(), event)
432 }
433
434 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 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 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
540fn 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#[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}