Skip to main content

runlimit_memory/
store.rs

1use std::{
2    fmt,
3    sync::Arc,
4    time::{Duration, Instant},
5};
6
7use runlimit_core::{
8    AdmissionObservation, BatchDecision, BatchError, CapacityObservation, Check,
9    CleanupObservation, ConsumptionStatus, CounterKey, Decision, Denial, Limiter, Observation,
10    Observer, QuotaDenial, observe_safely, validate_batch,
11};
12use thiserror::Error;
13
14use crate::{
15    Clock, MemoryStoreConfig, SystemClock,
16    shards::{
17        BatchTopology, BoundedShards, CleanupEffect, Shard, ShardEffect, collect_shard_effects,
18        usize_to_u64,
19    },
20};
21
22#[derive(Clone, Copy, Debug, Eq, PartialEq)]
23struct Entry {
24    used: u64,
25}
26
27impl Shard<Entry> {
28    fn quota_denial(&self, check: &PreparedCheck, now_millis: u128) -> Option<QuotaDenial> {
29        let (entry, expires_at_millis) = self.active_entry(check.counter_key, now_millis)?;
30        let remaining = remaining_quota(check.limit, entry.used);
31        (check.cost > remaining).then(|| {
32            QuotaDenial::try_new(
33                check.limit,
34                duration_from_millis(expires_at_millis.saturating_sub(now_millis)),
35            )
36            .expect("prepared policy limits are validated")
37        })
38    }
39
40    fn consume(&mut self, check: &PreparedCheck, now_millis: u128) -> Decision {
41        let expires_at_millis = now_millis + u128::from(check.window_millis);
42        if let Some((entry, active_expires_at_millis)) =
43            self.active_entry(check.counter_key, now_millis)
44        {
45            let remaining = remaining_quota(check.limit, entry.used);
46            debug_assert!(
47                check.cost <= remaining,
48                "quota denial must be checked before consumption"
49            );
50            self.update_value(check.counter_key, |entry| {
51                entry.used = entry.used.saturating_add(check.cost);
52            })
53            .expect("the active entry was present");
54            return Decision::allowed(
55                check.limit,
56                remaining.saturating_sub(check.cost),
57                duration_from_millis(active_expires_at_millis.saturating_sub(now_millis)),
58            );
59        }
60
61        self.replace(
62            check.counter_key,
63            Entry { used: check.cost },
64            expires_at_millis,
65        );
66        Decision::allowed(
67            check.limit,
68            remaining_quota(check.limit, check.cost),
69            duration_from_millis(expires_at_millis.saturating_sub(now_millis)),
70        )
71    }
72}
73
74#[derive(Debug)]
75struct PreparedCheck {
76    input_index: usize,
77    counter_key: CounterKey,
78    shard_position: usize,
79    limit: u64,
80    window_millis: u64,
81    cost: u64,
82}
83
84impl PreparedCheck {
85    fn new(input_index: usize, check: &Check<'_>, shard_position: usize) -> Self {
86        Self {
87            input_index,
88            counter_key: check.counter_key(),
89            shard_position,
90            limit: check.policy().limit(),
91            window_millis: check.policy().window_millis(),
92            cost: check.cost(),
93        }
94    }
95}
96
97#[derive(Debug)]
98struct Evaluation<T, E> {
99    value: T,
100    effect: E,
101}
102
103/// A sharded, hard-bounded, process-local fixed-window store.
104///
105/// The store never evicts an active key to admit a new one. Every check touches
106/// only the shards required by that check and performs a bounded amount of
107/// expiry cleanup. An atomic batch locks its shards in deterministic order.
108///
109/// If application code panics while a shard is locked, that shard remains
110/// poisoned and every later operation touching it fails closed with
111/// [`MemoryStoreError::PoisonedShard`]. [`MemoryStore::recover_poisoned`] is an
112/// explicit availability tradeoff: it restores poisoned shards by discarding
113/// their counters rather than trusting state whose consistency is unknown.
114pub struct MemoryStore<C = SystemClock> {
115    config: MemoryStoreConfig,
116    clock: C,
117    shards: BoundedShards<Entry>,
118    observer: Option<Arc<dyn Observer>>,
119}
120
121impl<C> fmt::Debug for MemoryStore<C> {
122    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
123        let poisoned_shards = self.shards.poisoned_count();
124
125        formatter
126            .debug_struct("MemoryStore")
127            .field("config", &self.config)
128            .field("has_observer", &self.observer.is_some())
129            .field("poisoned_shards", &poisoned_shards)
130            .field("shard_state", &Redacted)
131            .finish_non_exhaustive()
132    }
133}
134
135struct Redacted;
136
137impl fmt::Debug for Redacted {
138    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
139        formatter.write_str("[REDACTED]")
140    }
141}
142
143impl MemoryStore<SystemClock> {
144    /// Creates a store using the system monotonic clock.
145    pub fn new(config: MemoryStoreConfig) -> Self {
146        Self::with_clock(config, SystemClock::new())
147    }
148}
149
150impl<C: Clock> MemoryStore<C> {
151    /// Creates a store using a caller-supplied monotonic clock.
152    ///
153    /// Supplying a clock is primarily useful for deterministic tests.
154    pub fn with_clock(config: MemoryStoreConfig, clock: C) -> Self {
155        let shards = BoundedShards::new(&config);
156
157        Self {
158            config,
159            clock,
160            shards,
161            observer: None,
162        }
163    }
164
165    /// Returns this store with an operational observer.
166    ///
167    /// Observer callbacks run after internal locks are released. A callback
168    /// panic is isolated and cannot change the admission result.
169    #[must_use]
170    pub fn with_observer(mut self, observer: Arc<dyn Observer>) -> Self {
171        self.observer = Some(observer);
172        self
173    }
174
175    fn observe_shard_effects(&self, effects: &[ShardEffect]) {
176        for effect in effects {
177            self.observe_shard_effect(effect);
178        }
179    }
180
181    fn observe_shard_effect(&self, effect: &ShardEffect) {
182        let Some(observer) = &self.observer else {
183            return;
184        };
185
186        observe_safely(
187            observer.as_ref(),
188            &Observation::Cleanup(CleanupObservation::confirmed(
189                effect.cleanup.requested,
190                usize_to_u64(effect.cleanup.removed),
191                effect.cleanup.elapsed,
192            )),
193        );
194        observe_safely(
195            observer.as_ref(),
196            &Observation::Capacity(CapacityObservation::new(
197                usize_to_u64(effect.used),
198                usize_to_u64(effect.capacity),
199                Some(effect.shard_index),
200            )),
201        );
202    }
203
204    fn observe_admission<'a>(&self, build_observation: impl FnOnce() -> AdmissionObservation<'a>) {
205        let Some(observer) = &self.observer else {
206            return;
207        };
208        let admission = build_observation();
209        observe_safely(observer.as_ref(), &Observation::Admission(admission));
210    }
211
212    /// Evaluates and, when allowed, consumes one check.
213    ///
214    /// # Errors
215    ///
216    /// Returns an error without allowing the request when the target shard is
217    /// poisoned.
218    pub fn check(&self, check: &Check<'_>) -> Result<Decision, MemoryStoreError> {
219        let started = Instant::now();
220        let result = self.check_inner(check);
221        let elapsed = started.elapsed();
222
223        match &result {
224            Ok(evaluation) => {
225                self.observe_shard_effect(&evaluation.effect);
226                self.observe_admission(|| {
227                    AdmissionObservation::from_check(check, &evaluation.value, elapsed)
228                });
229            }
230            Err(_) => self.observe_admission(|| {
231                AdmissionObservation::failed_check(check, ConsumptionStatus::NotConsumed, elapsed)
232            }),
233        }
234
235        result.map(|evaluation| evaluation.value)
236    }
237
238    fn check_inner(
239        &self,
240        check: &Check<'_>,
241    ) -> Result<Evaluation<Decision, ShardEffect>, MemoryStoreError> {
242        let counter_key = check.counter_key();
243        let shard_index = self.shards.shard_index(&counter_key);
244        let prepared = PreparedCheck::new(0, check, 0);
245        let mut shard = self.shards.lock_shard(shard_index)?;
246        let observed_millis = self.clock.now().as_millis();
247        let now_millis = observed_millis.max(shard.latest_observed_millis());
248        shard.record_observed_millis(now_millis);
249        let cleanup_requested = self.config.max_expired_removals_per_check();
250        let cleanup_started = Instant::now();
251        let cleanup_removed = shard.prune_expired(now_millis, cleanup_requested);
252        let cleanup_elapsed = cleanup_started.elapsed();
253
254        let decision = if let Some(denial) = shard.quota_denial(&prepared, now_millis) {
255            if check.policy().quota_mode() == runlimit_core::QuotaMode::Shadow {
256                Decision::shadow_denied(denial)
257            } else {
258                Decision::denied(denial)
259            }
260        } else if !shard.contains_key(counter_key) && shard.used() >= shard.capacity() {
261            Decision::denied(Denial::storage_capacity(
262                shard
263                    .capacity_retry_after_millis(now_millis)
264                    .map(duration_from_millis),
265            ))
266        } else {
267            shard.consume(&prepared, now_millis)
268        };
269
270        Ok(Evaluation {
271            value: decision,
272            effect: ShardEffect {
273                shard_index,
274                cleanup: CleanupEffect {
275                    requested: cleanup_requested,
276                    removed: cleanup_removed,
277                    elapsed: cleanup_elapsed,
278                },
279                used: shard.used(),
280                capacity: shard.capacity(),
281            },
282        })
283    }
284
285    /// Evaluates a batch atomically.
286    ///
287    /// If any check is denied, none of the checks consumes quota. Returned
288    /// allowed decisions preserve input order.
289    ///
290    /// # Errors
291    ///
292    /// Returns an error before quota consumption when the batch exceeds its
293    /// configured bound, contains a duplicate key, targets more distinct keys
294    /// at one shard than that shard can ever store, or a touched shard is
295    /// poisoned.
296    ///
297    #[allow(clippy::too_many_lines)]
298    pub fn check_all(&self, checks: &[Check<'_>]) -> Result<BatchDecision, MemoryStoreError> {
299        let started = Instant::now();
300        let result = self.check_all_inner(checks);
301        let elapsed = started.elapsed();
302
303        match &result {
304            Ok(evaluation) => {
305                self.observe_shard_effects(&evaluation.effect);
306                self.observe_admission(|| {
307                    AdmissionObservation::from_batch(checks, &evaluation.value, elapsed)
308                });
309            }
310            Err(_) => self.observe_admission(|| {
311                AdmissionObservation::failed_batch(
312                    checks.len(),
313                    ConsumptionStatus::NotConsumed,
314                    elapsed,
315                )
316            }),
317        }
318
319        result.map(|evaluation| evaluation.value)
320    }
321
322    #[allow(clippy::too_many_lines)]
323    fn check_all_inner(
324        &self,
325        checks: &[Check<'_>],
326    ) -> Result<Evaluation<BatchDecision, Vec<ShardEffect>>, MemoryStoreError> {
327        validate_batch(checks, self.config.max_batch_size())?;
328        if checks.is_empty() {
329            return Ok(Evaluation {
330                value: BatchDecision::allowed(Vec::new()),
331                effect: Vec::new(),
332            });
333        }
334
335        let topology = BatchTopology::new(
336            checks
337                .iter()
338                .map(|check| self.shards.shard_index(&check.counter_key())),
339            &self.config,
340        )?;
341        let prepared = checks
342            .iter()
343            .enumerate()
344            .map(|(input_index, check)| {
345                PreparedCheck::new(input_index, check, topology.shard_position(input_index))
346            })
347            .collect::<Vec<_>>();
348
349        let mut locked_shards = self.shards.lock_topology(&topology)?;
350        let observed_millis = self.clock.now().as_millis();
351        let now_millis = locked_shards
352            .iter()
353            .map(|(_, shard)| shard.latest_observed_millis())
354            .fold(observed_millis, u128::max);
355        let mut cleanup_effects = Vec::with_capacity(locked_shards.len());
356        for ((_, shard), check_count) in locked_shards.iter_mut().zip(topology.check_counts()) {
357            shard.record_observed_millis(now_millis);
358            let cleanup_limit = self
359                .config
360                .max_expired_removals_per_check()
361                .saturating_mul(check_count);
362            let cleanup_started = Instant::now();
363            let removed = shard.prune_expired(now_millis, cleanup_limit);
364            cleanup_effects.push(CleanupEffect {
365                requested: cleanup_limit,
366                removed,
367                elapsed: cleanup_started.elapsed(),
368            });
369        }
370
371        let mut pending_insertions = vec![0_usize; locked_shards.len()];
372        for check in &prepared {
373            let shard = &locked_shards[check.shard_position].1;
374            if let Some(denial) = shard.quota_denial(check, now_millis) {
375                let value = if checks[check.input_index].policy().quota_mode()
376                    == runlimit_core::QuotaMode::Shadow
377                {
378                    BatchDecision::shadow_denied(check.input_index, denial)
379                } else {
380                    BatchDecision::denied(check.input_index, denial)
381                };
382                return Ok(Evaluation {
383                    value,
384                    effect: collect_shard_effects(&locked_shards, &cleanup_effects),
385                });
386            }
387
388            if !shard.contains_key(check.counter_key) {
389                let projected_len = shard.used() + pending_insertions[check.shard_position];
390                if projected_len >= shard.capacity() {
391                    return Ok(Evaluation {
392                        value: BatchDecision::denied(
393                            check.input_index,
394                            Denial::storage_capacity(
395                                shard
396                                    .capacity_retry_after_millis(now_millis)
397                                    .map(duration_from_millis),
398                            ),
399                        ),
400                        effect: collect_shard_effects(&locked_shards, &cleanup_effects),
401                    });
402                }
403                pending_insertions[check.shard_position] += 1;
404            }
405        }
406
407        let mut decisions = Vec::with_capacity(prepared.len());
408        for check in &prepared {
409            let shard = &mut locked_shards[check.shard_position].1;
410            decisions.push(shard.consume(check, now_millis));
411        }
412
413        Ok(Evaluation {
414            value: BatchDecision::allowed(decisions),
415            effect: collect_shard_effects(&locked_shards, &cleanup_effects),
416        })
417    }
418
419    /// Returns current storage usage.
420    ///
421    /// # Errors
422    ///
423    /// Returns an error if a shard is poisoned.
424    pub fn stats(&self) -> Result<MemoryStoreStats, MemoryStoreError> {
425        self.shards.stats(&self.config)
426    }
427
428    /// Removes every stored counter.
429    ///
430    /// # Errors
431    ///
432    /// Returns an error if a shard is poisoned.
433    pub fn clear(&self) -> Result<(), MemoryStoreError> {
434        self.shards.clear()
435    }
436
437    /// Rebuilds every poisoned shard and returns the number recovered.
438    ///
439    /// A poisoned shard's internal consistency is unknown, so recovery
440    /// discards all counters in that shard before clearing its mutex poison
441    /// flag. This can admit requests that the discarded counters would have
442    /// denied. Healthy shards and their active counters are left unchanged.
443    ///
444    /// Until this method is called, operations touching a poisoned shard
445    /// continue to fail closed with [`MemoryStoreError::PoisonedShard`].
446    /// Recovery is safe to invoke through an [`std::sync::Arc`]. It locks every
447    /// shard in index order before changing any of them, so concurrent checks
448    /// observe either the pre-recovery poisoned store or the complete recovered
449    /// state, never a partially reopened multi-shard store.
450    pub fn recover_poisoned(&self) -> usize {
451        self.shards.recover_poisoned(&self.config)
452    }
453}
454
455fn remaining_quota(limit: u64, used: u64) -> u64 {
456    debug_assert!(
457        used <= limit,
458        "stored quota usage ({used}) exceeded its policy limit ({limit})"
459    );
460    limit.saturating_sub(used)
461}
462
463impl<C: Clock> Limiter for MemoryStore<C> {
464    type Policy = runlimit_core::FixedWindowPolicy;
465    type Error = MemoryStoreError;
466
467    fn check(
468        &self,
469        check: &Check<'_>,
470    ) -> impl Future<Output = Result<Decision, Self::Error>> + Send {
471        std::future::ready(MemoryStore::check(self, check))
472    }
473
474    fn check_all(
475        &self,
476        checks: &[Check<'_>],
477    ) -> impl Future<Output = Result<BatchDecision, Self::Error>> + Send {
478        std::future::ready(MemoryStore::check_all(self, checks))
479    }
480}
481
482fn duration_from_millis(millis: u128) -> Duration {
483    Duration::from_millis(
484        u64::try_from(millis)
485            .expect("a counter's remaining duration cannot exceed its portable policy window"),
486    )
487}
488
489/// Current bounded-store usage.
490///
491/// With the `serde` feature, this serializes as an object containing `entries`,
492/// `capacity`, and `shard_count`. Telemetry is intentionally serialize-only.
493#[derive(Clone, Copy, Debug, Eq, PartialEq)]
494pub struct MemoryStoreStats {
495    entries: usize,
496    capacity: usize,
497    shard_count: usize,
498}
499
500impl MemoryStoreStats {
501    pub(crate) const fn from_parts(entries: usize, capacity: usize, shard_count: usize) -> Self {
502        Self {
503            entries,
504            capacity,
505            shard_count,
506        }
507    }
508
509    /// Returns the number of stored counters.
510    pub const fn entries(self) -> usize {
511        self.entries
512    }
513
514    /// Returns the hard maximum number of stored counters.
515    pub const fn capacity(self) -> usize {
516        self.capacity
517    }
518
519    /// Returns the number of independently locked shards.
520    pub const fn shard_count(self) -> usize {
521        self.shard_count
522    }
523}
524
525#[cfg(feature = "serde")]
526#[derive(serde::Serialize)]
527struct MemoryStoreStatsWire {
528    entries: usize,
529    capacity: usize,
530    shard_count: usize,
531}
532
533#[cfg(feature = "serde")]
534impl serde::Serialize for MemoryStoreStats {
535    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
536    where
537        S: serde::Serializer,
538    {
539        serde::Serialize::serialize(
540            &MemoryStoreStatsWire {
541                entries: self.entries(),
542                capacity: self.capacity(),
543                shard_count: self.shard_count(),
544            },
545            serializer,
546        )
547    }
548}
549
550/// A fail-closed in-memory store error.
551#[derive(Clone, Debug, Error, Eq, PartialEq)]
552pub enum MemoryStoreError {
553    /// The atomic batch violated a backend-independent structural requirement.
554    #[error(transparent)]
555    InvalidBatch(#[from] BatchError),
556    /// An atomic batch can never fit in one shard, regardless of expiry.
557    #[error(
558        "batch targets {key_count} distinct keys at memory-store shard {shard_index}, \
559         but that shard can store at most {capacity}"
560    )]
561    BatchExceedsShardCapacity {
562        /// Index of the shard that cannot hold all targeted keys.
563        shard_index: usize,
564        /// Number of distinct batch keys targeting the shard.
565        key_count: usize,
566        /// Hard key capacity of the shard.
567        capacity: usize,
568    },
569    /// A shard mutex was poisoned and remains unavailable.
570    #[error("memory-store shard {shard_index} is poisoned and unavailable")]
571    PoisonedShard {
572        /// Poisoned shard index.
573        shard_index: usize,
574    },
575}
576
577#[cfg(test)]
578mod tests {
579    use std::{
580        sync::{
581            Arc, Barrier, Mutex, Weak,
582            atomic::{AtomicBool, AtomicU64, AtomicUsize, Ordering},
583            mpsc,
584        },
585        thread,
586        time::Duration,
587    };
588
589    use runlimit_core::{
590        AdmissionOperation, AdmissionOutcome, BatchDecision, BatchError, Check, ConsumptionStatus,
591        Decision, Denial, DenialKind, FixedWindowPolicy, KeyHasher, MAX_LIMIT, MAX_WINDOW,
592        MAX_WINDOW_MILLIS, Observation, Observer, PolicyId, QuotaDenial, QuotaMode, ScopeId,
593        SubjectKey,
594    };
595
596    use super::{Entry, MemoryStore, MemoryStoreError, remaining_quota};
597    use crate::{Clock, MemoryStoreConfig, shards::counter_key_hash};
598
599    fn quota(capacity: u64, retry_after: Duration) -> QuotaDenial {
600        QuotaDenial::try_new(capacity, retry_after).unwrap()
601    }
602
603    #[derive(Clone, Default)]
604    struct ManualClock {
605        now_millis: Arc<AtomicU64>,
606    }
607
608    impl ManualClock {
609        fn advance(&self, duration: Duration) {
610            let millis = u64::try_from(duration.as_millis()).unwrap();
611            self.now_millis.fetch_add(millis, Ordering::Relaxed);
612        }
613
614        fn set(&self, duration: Duration) {
615            let millis = u64::try_from(duration.as_millis()).unwrap();
616            self.now_millis.store(millis, Ordering::Relaxed);
617        }
618    }
619
620    impl Clock for ManualClock {
621        fn now(&self) -> Duration {
622            Duration::from_millis(self.now_millis.load(Ordering::Relaxed))
623        }
624    }
625
626    #[derive(Clone, Default)]
627    struct PanicOnceClock {
628        panic_next: Arc<AtomicBool>,
629    }
630
631    impl PanicOnceClock {
632        fn panic_once(&self) {
633            self.panic_next.store(true, Ordering::Relaxed);
634        }
635    }
636
637    impl Clock for PanicOnceClock {
638        fn now(&self) -> Duration {
639            assert!(
640                !self.panic_next.swap(false, Ordering::Relaxed),
641                "panic from test clock"
642            );
643            Duration::ZERO
644        }
645    }
646
647    #[derive(Clone)]
648    struct WideManualClock {
649        now_millis: Arc<Mutex<u128>>,
650    }
651
652    impl WideManualClock {
653        fn new(now_millis: u128) -> Self {
654            Self {
655                now_millis: Arc::new(Mutex::new(now_millis)),
656            }
657        }
658
659        fn advance(&self, millis: u128) {
660            let mut now_millis = self.now_millis.lock().unwrap();
661            *now_millis += millis;
662        }
663    }
664
665    impl Clock for WideManualClock {
666        fn now(&self) -> Duration {
667            let millis = *self.now_millis.lock().unwrap();
668            let seconds = u64::try_from(millis / 1_000).unwrap();
669            let subsec_millis = u32::try_from(millis % 1_000).unwrap();
670            Duration::new(seconds, subsec_millis * 1_000_000)
671        }
672    }
673
674    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
675    enum RecordedObservation {
676        Admission(AdmissionOutcome, ConsumptionStatus, usize),
677        Cleanup(usize, Option<u64>),
678        Capacity(u64, u64, u64),
679    }
680
681    #[derive(Default)]
682    struct RecordingObserver {
683        observations: Mutex<Vec<RecordedObservation>>,
684    }
685
686    impl Observer for RecordingObserver {
687        fn observe(&self, observation: &Observation<'_>) {
688            let owned = match observation {
689                Observation::Admission(admission) => RecordedObservation::Admission(
690                    admission.outcome(),
691                    admission.consumption(),
692                    admission.batch_size(),
693                ),
694                Observation::Cleanup(cleanup) => {
695                    RecordedObservation::Cleanup(cleanup.requested(), cleanup.removed())
696                }
697                Observation::Capacity(capacity) => RecordedObservation::Capacity(
698                    capacity.used(),
699                    capacity.capacity(),
700                    capacity.headroom(),
701                ),
702                _ => return,
703            };
704            self.observations.lock().unwrap().push(owned);
705        }
706    }
707
708    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
709    struct RecordedAdmissionMetadata {
710        operation: AdmissionOperation,
711        batch_size: usize,
712        has_policy_id: bool,
713        has_scope_id: bool,
714        has_policy_fingerprint: bool,
715        outcome: AdmissionOutcome,
716        consumption: ConsumptionStatus,
717    }
718
719    #[derive(Default)]
720    struct AdmissionMetadataObserver {
721        admissions: Mutex<Vec<RecordedAdmissionMetadata>>,
722    }
723
724    impl Observer for AdmissionMetadataObserver {
725        fn observe(&self, observation: &Observation<'_>) {
726            let Observation::Admission(admission) = observation else {
727                return;
728            };
729            self.admissions
730                .lock()
731                .unwrap()
732                .push(RecordedAdmissionMetadata {
733                    operation: admission.operation(),
734                    batch_size: admission.batch_size(),
735                    has_policy_id: admission.policy_id().is_some(),
736                    has_scope_id: admission.scope_id().is_some(),
737                    has_policy_fingerprint: admission.policy_fingerprint().is_some(),
738                    outcome: admission.outcome(),
739                    consumption: admission.consumption(),
740                });
741        }
742    }
743
744    struct ReentrantObserver {
745        store: Mutex<Option<Weak<MemoryStore<ManualClock>>>>,
746        calls: AtomicUsize,
747    }
748
749    impl Observer for ReentrantObserver {
750        fn observe(&self, _observation: &Observation<'_>) {
751            self.calls.fetch_add(1, Ordering::Relaxed);
752            if let Some(store) = self.store.lock().unwrap().as_ref().and_then(Weak::upgrade) {
753                store.stats().unwrap();
754            }
755        }
756    }
757
758    struct PanickingObserver;
759
760    impl Observer for PanickingObserver {
761        fn observe(&self, _observation: &Observation<'_>) {
762            panic!("observer failure");
763        }
764    }
765
766    fn policy(policy_id: &str, scope_id: &str, limit: u64, window: Duration) -> FixedWindowPolicy {
767        FixedWindowPolicy::new(
768            PolicyId::new(policy_id).unwrap(),
769            ScopeId::new(scope_id).unwrap(),
770            limit,
771            window,
772        )
773        .unwrap()
774    }
775
776    fn subject(byte: u8) -> SubjectKey {
777        SubjectKey::from_digest([byte; 32])
778    }
779
780    fn subjects_for_shard<C: Clock>(
781        store: &MemoryStore<C>,
782        policy: &FixedWindowPolicy,
783        shard_index: usize,
784        count: usize,
785    ) -> Vec<SubjectKey> {
786        assert!(shard_index < store.shards.len());
787        let mut subjects = Vec::with_capacity(count);
788
789        for value in 0_u64..10_000 {
790            let mut digest = [0_u8; 32];
791            digest[..8].copy_from_slice(&value.to_le_bytes());
792            let candidate = SubjectKey::from_digest(digest);
793            let counter_key = Check::new(policy, candidate).counter_key();
794            if store.shards.shard_index(&counter_key) == shard_index {
795                subjects.push(candidate);
796                if subjects.len() == count {
797                    break;
798                }
799            }
800        }
801
802        assert_eq!(
803            subjects.len(),
804            count,
805            "could not find enough subjects for shard {shard_index}"
806        );
807        subjects
808    }
809
810    #[test]
811    fn hmac_subjects_are_evenly_and_deterministically_sharded() {
812        const SHARD_COUNT: usize = 16;
813        const SUBJECT_COUNT: u64 = 4_096;
814
815        let config = MemoryStoreConfig::new(SHARD_COUNT)
816            .unwrap()
817            .with_shard_count(SHARD_COUNT)
818            .unwrap();
819        let first = MemoryStore::with_clock(config.clone(), ManualClock::default());
820        let second = MemoryStore::with_clock(config, ManualClock::default());
821        let policy = policy("auth.login", "client", 2, Duration::from_secs(60));
822        let key_hasher = KeyHasher::new([0x42; 32]).unwrap();
823        let mut counts = [0_usize; SHARD_COUNT];
824
825        for value in 0_u64..SUBJECT_COUNT {
826            let subject = key_hasher.hash_for(&policy, value.to_le_bytes());
827            let key = Check::new(&policy, subject).counter_key();
828            let first_index = first.shards.shard_index(&key);
829
830            assert_eq!(first_index, second.shards.shard_index(&key));
831            counts[first_index] += 1;
832        }
833
834        assert!(
835            counts.iter().all(|&count| (176..=336).contains(&count)),
836            "uniform HMAC output should spread across every shard: {counts:?}"
837        );
838    }
839
840    #[test]
841    fn the_entries_map_distinguishes_deliberate_prehash_collisions() {
842        let first_policy = policy("auth.login", "client", 1, Duration::from_secs(60));
843        let second_policy = policy("auth.reset", "client", 2, Duration::from_secs(60));
844        let first_subject = SubjectKey::from_digest([0_u8; 32]);
845        let first_key = Check::new(&first_policy, first_subject).counter_key();
846
847        let zero_second_key =
848            Check::new(&second_policy, SubjectKey::from_digest([0_u8; 32])).counter_key();
849        let colliding_subject_word =
850            counter_key_hash(first_key) ^ counter_key_hash(zero_second_key);
851        let mut second_digest = [0_u8; 32];
852        second_digest[..8].copy_from_slice(&colliding_subject_word.to_le_bytes());
853        let second_subject = SubjectKey::from_digest(second_digest);
854        let second_key = Check::new(&second_policy, second_subject).counter_key();
855
856        assert_ne!(first_key, second_key);
857        assert_eq!(counter_key_hash(first_key), counter_key_hash(second_key));
858
859        let store =
860            MemoryStore::with_clock(MemoryStoreConfig::new(4).unwrap(), ManualClock::default());
861        let first_check = Check::new(&first_policy, first_subject);
862        let second_check = Check::new(&second_policy, second_subject);
863
864        assert!(store.check(&first_check).unwrap().is_allowed());
865        assert!(store.check(&second_check).unwrap().is_allowed());
866        assert_eq!(store.stats().unwrap().entries(), 2);
867        assert!(store.check(&first_check).unwrap().is_denied());
868        assert!(store.check(&second_check).unwrap().is_allowed());
869    }
870
871    #[test]
872    fn remaining_quota_reaches_zero_without_wrapping() {
873        assert_eq!(remaining_quota(3, 0), 3);
874        assert_eq!(remaining_quota(3, 3), 0);
875    }
876
877    #[cfg(debug_assertions)]
878    #[test]
879    #[should_panic(expected = "stored quota usage (4) exceeded its policy limit (3)")]
880    fn corrupt_quota_state_trips_the_debug_invariant() {
881        let _ = remaining_quota(3, 4);
882    }
883
884    #[cfg(not(debug_assertions))]
885    #[test]
886    fn corrupt_quota_state_fails_closed_in_release_builds() {
887        let policy = policy("auth.login", "client", 3, Duration::from_secs(60));
888        let check = Check::new(&policy, subject(1));
889        let key = check.counter_key();
890        let store =
891            MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default());
892        {
893            let mut shard = store.shards.shard(0).lock().unwrap();
894            assert!(shard.replace(key, Entry { used: 4 }, 60_000).is_none());
895        }
896
897        assert_eq!(
898            store.check(&check),
899            Ok(Decision::denied(quota(3, Duration::from_secs(60))))
900        );
901    }
902
903    #[test]
904    fn debug_output_is_useful_without_exposing_counter_state() {
905        let store =
906            MemoryStore::with_clock(MemoryStoreConfig::new(8).unwrap(), ManualClock::default());
907        let policy = policy("auth.login", "client", 2, Duration::from_secs(60));
908        store
909            .check(&Check::new(&policy, subject(0xab)))
910            .expect("store is available");
911
912        let output = format!("{store:?}");
913
914        assert!(output.starts_with("MemoryStore { config: MemoryStoreConfig"));
915        assert!(output.contains("max_keys: 8"));
916        assert!(output.contains("poisoned_shards: 0"));
917        assert!(output.contains("shard_state: [REDACTED]"));
918        assert!(!output.contains("CounterKey"));
919        assert!(!output.contains("expires_at_millis"));
920        assert!(!output.contains("used:"));
921    }
922
923    #[test]
924    fn enforces_quota_and_reports_exact_retry_duration() {
925        let clock = ManualClock::default();
926        let store = MemoryStore::with_clock(MemoryStoreConfig::new(8).unwrap(), clock.clone());
927        let policy = policy("auth.login", "client", 2, Duration::from_secs(60));
928        let check = Check::new(&policy, subject(1));
929
930        let first = store.check(&check).unwrap();
931        assert!(first.is_allowed());
932        assert_eq!(first.available(), Some(1));
933        assert_eq!(first.retry_after(), None);
934
935        let second = store.check(&check).unwrap();
936        assert!(second.is_allowed());
937        assert_eq!(second.available(), Some(0));
938
939        let denied = store.check(&check).unwrap();
940        assert!(!denied.is_allowed());
941        assert_eq!(denied.retry_after(), Some(Duration::from_secs(60)));
942
943        clock.advance(Duration::from_secs(10));
944        assert_eq!(
945            store.check(&check).unwrap().retry_after(),
946            Some(Duration::from_secs(50))
947        );
948
949        clock.advance(Duration::from_secs(50));
950        let reset = store.check(&check).unwrap();
951        assert!(reset.is_allowed());
952        assert_eq!(reset.available(), Some(1));
953        assert_eq!(reset.replenishes_after(), Some(Duration::from_secs(60)));
954    }
955
956    #[test]
957    fn shadow_mode_reports_quota_without_consuming_or_rejecting() {
958        let clock = ManualClock::default();
959        let store = MemoryStore::with_clock(MemoryStoreConfig::new(4).unwrap(), clock.clone());
960        let enforced = policy("auth.login", "client", 1, Duration::from_secs(60));
961        let shadow = enforced.clone().with_quota_mode(QuotaMode::Shadow);
962        let subject = subject(7);
963
964        assert!(
965            store
966                .check(&Check::new(&shadow, subject))
967                .unwrap()
968                .is_allowed()
969        );
970        let shadow_denial = store.check(&Check::new(&shadow, subject)).unwrap();
971        assert!(shadow_denial.permits_request());
972        assert!(shadow_denial.is_shadow_denied());
973        assert_eq!(
974            shadow_denial.denial().map(Denial::kind),
975            Some(DenialKind::QuotaExceeded)
976        );
977
978        let enforced_denial = store.check(&Check::new(&enforced, subject)).unwrap();
979        assert!(enforced_denial.is_enforced_denial());
980        assert_eq!(
981            enforced_denial.denial().map(Denial::kind),
982            Some(DenialKind::QuotaExceeded)
983        );
984
985        clock.advance(Duration::from_secs(60));
986        assert!(
987            store
988                .check(&Check::new(&enforced, subject))
989                .unwrap()
990                .is_allowed()
991        );
992    }
993
994    #[test]
995    fn shadow_batches_roll_back_and_capacity_denials_remain_enforced() {
996        let store =
997            MemoryStore::with_clock(MemoryStoreConfig::new(3).unwrap(), ManualClock::default());
998        let shadow = policy("auth.login", "client", 1, Duration::from_secs(60))
999            .with_quota_mode(QuotaMode::Shadow);
1000        let first = Check::new(&shadow, subject(1));
1001        let second = Check::new(&shadow, subject(2));
1002
1003        assert!(store.check(&first).unwrap().is_allowed());
1004        let result = store.check_all(&[first, second]).unwrap();
1005        assert!(result.is_shadow_denied());
1006        assert_eq!(result.denied_index(), Some(0));
1007        assert!(
1008            store.check(&second).unwrap().is_allowed(),
1009            "a shadow-denied atomic batch must not consume another check"
1010        );
1011
1012        let full_store =
1013            MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default());
1014        assert!(full_store.check(&first).unwrap().is_allowed());
1015        let capacity = full_store.check(&second).unwrap();
1016        assert!(capacity.is_enforced_denial());
1017        assert_eq!(
1018            capacity.denial().map(Denial::kind),
1019            Some(DenialKind::StorageCapacity)
1020        );
1021    }
1022
1023    #[test]
1024    fn mixed_shadow_and_enforced_batches_fail_before_consumption() {
1025        let store =
1026            MemoryStore::with_clock(MemoryStoreConfig::new(4).unwrap(), ManualClock::default());
1027        let enforced = policy("auth.login", "client", 1, Duration::from_secs(60));
1028        let shadow = policy("auth.reset", "client", 1, Duration::from_secs(60))
1029            .with_quota_mode(QuotaMode::Shadow);
1030        let result = store.check_all(&[
1031            Check::new(&enforced, subject(1)),
1032            Check::new(&shadow, subject(2)),
1033        ]);
1034
1035        assert!(matches!(
1036            result,
1037            Err(MemoryStoreError::InvalidBatch(
1038                BatchError::MixedQuotaModes { index: 1, .. }
1039            ))
1040        ));
1041        assert_eq!(store.stats().unwrap().entries(), 0);
1042    }
1043
1044    #[test]
1045    fn observer_reports_outcomes_cleanup_and_capacity_headroom() {
1046        let observer = Arc::new(RecordingObserver::default());
1047        let store =
1048            MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default())
1049                .with_observer(observer.clone());
1050        let limited = policy("auth.login", "client", 1, Duration::from_secs(60));
1051
1052        assert!(
1053            store
1054                .check(&Check::new(&limited, subject(1)))
1055                .unwrap()
1056                .is_allowed()
1057        );
1058        assert!(
1059            store
1060                .check(&Check::new(&limited, subject(1)))
1061                .unwrap()
1062                .is_denied()
1063        );
1064        assert!(
1065            store
1066                .check(&Check::new(&limited, subject(2)))
1067                .unwrap()
1068                .is_denied()
1069        );
1070
1071        let observations = observer.observations.lock().unwrap().clone();
1072        assert_eq!(observations.len(), 9);
1073        assert!(observations.contains(&RecordedObservation::Admission(
1074            AdmissionOutcome::Allowed,
1075            ConsumptionStatus::Consumed,
1076            1,
1077        )));
1078        assert!(observations.contains(&RecordedObservation::Admission(
1079            AdmissionOutcome::QuotaDenied,
1080            ConsumptionStatus::NotConsumed,
1081            1,
1082        )));
1083        assert!(observations.contains(&RecordedObservation::Admission(
1084            AdmissionOutcome::CapacityDenied,
1085            ConsumptionStatus::NotConsumed,
1086            1,
1087        )));
1088        assert_eq!(
1089            observations
1090                .iter()
1091                .filter(|event| matches!(event, RecordedObservation::Cleanup(8, Some(0))))
1092                .count(),
1093            3
1094        );
1095        assert_eq!(
1096            observations
1097                .iter()
1098                .filter(|event| matches!(event, RecordedObservation::Capacity(1, 1, 0)))
1099                .count(),
1100            3
1101        );
1102    }
1103
1104    #[test]
1105    fn observers_run_after_unlock_and_panics_are_isolated() {
1106        let observer = Arc::new(ReentrantObserver {
1107            store: Mutex::new(None),
1108            calls: AtomicUsize::new(0),
1109        });
1110        let store = Arc::new(
1111            MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default())
1112                .with_observer(observer.clone()),
1113        );
1114        *observer.store.lock().unwrap() = Some(Arc::downgrade(&store));
1115        let limited = policy("auth.login", "client", 1, Duration::from_secs(60));
1116        let check = Check::new(&limited, subject(1));
1117
1118        assert!(store.check(&check).unwrap().is_allowed());
1119        assert_eq!(observer.calls.load(Ordering::Relaxed), 3);
1120
1121        let panicking_store =
1122            MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default())
1123                .with_observer(Arc::new(PanickingObserver));
1124        assert!(panicking_store.check(&check).unwrap().is_allowed());
1125        assert!(panicking_store.check(&check).unwrap().is_denied());
1126    }
1127
1128    #[test]
1129    fn single_check_matches_a_one_element_batch_across_state_transitions() {
1130        #[derive(Clone, Copy)]
1131        struct Step {
1132            now: Duration,
1133            subject: u8,
1134            cost: u64,
1135            expected: Decision,
1136        }
1137
1138        let config = MemoryStoreConfig::new(2)
1139            .unwrap()
1140            .with_shard_count(1)
1141            .unwrap()
1142            .with_max_expired_removals_per_check(1)
1143            .unwrap();
1144        let single_clock = ManualClock::default();
1145        let batch_clock = ManualClock::default();
1146        let single_store = MemoryStore::with_clock(config.clone(), single_clock.clone());
1147        let batch_store = MemoryStore::with_clock(config, batch_clock.clone());
1148        let policy = policy("auth.login", "client", 5, Duration::from_millis(10));
1149        let steps = [
1150            Step {
1151                now: Duration::ZERO,
1152                subject: 1,
1153                cost: 2,
1154                expected: Decision::allowed(5, 3, Duration::from_millis(10)),
1155            },
1156            Step {
1157                now: Duration::from_millis(3),
1158                subject: 1,
1159                cost: 2,
1160                expected: Decision::allowed(5, 1, Duration::from_millis(7)),
1161            },
1162            Step {
1163                now: Duration::from_millis(3),
1164                subject: 1,
1165                cost: 2,
1166                expected: Decision::denied(quota(5, Duration::from_millis(7))),
1167            },
1168            Step {
1169                now: Duration::from_millis(9),
1170                subject: 1,
1171                cost: 1,
1172                expected: Decision::allowed(5, 0, Duration::from_millis(1)),
1173            },
1174            Step {
1175                now: Duration::from_millis(10),
1176                subject: 1,
1177                cost: 3,
1178                expected: Decision::allowed(5, 2, Duration::from_millis(10)),
1179            },
1180            Step {
1181                now: Duration::from_millis(8),
1182                subject: 1,
1183                cost: 1,
1184                expected: Decision::allowed(5, 1, Duration::from_millis(10)),
1185            },
1186            Step {
1187                now: Duration::from_millis(10),
1188                subject: 2,
1189                cost: 1,
1190                expected: Decision::allowed(5, 4, Duration::from_millis(10)),
1191            },
1192            Step {
1193                now: Duration::from_millis(10),
1194                subject: 3,
1195                cost: 1,
1196                expected: Decision::denied(Denial::storage_capacity(Some(Duration::from_millis(
1197                    10,
1198                )))),
1199            },
1200            Step {
1201                now: Duration::from_millis(20),
1202                subject: 3,
1203                cost: 1,
1204                expected: Decision::allowed(5, 4, Duration::from_millis(10)),
1205            },
1206        ];
1207
1208        for (index, step) in steps.into_iter().enumerate() {
1209            single_clock.set(step.now);
1210            batch_clock.set(step.now);
1211            let check = Check::with_cost(&policy, subject(step.subject), step.cost).unwrap();
1212
1213            let single = single_store.check(&check).unwrap();
1214            let batch = batch_store
1215                .check_all(std::slice::from_ref(&check))
1216                .unwrap()
1217                .try_into_single_decision()
1218                .expect("a one-element batch returns one decision");
1219
1220            assert_eq!(single, batch, "step {index}");
1221            assert_eq!(single, step.expected, "step {index}");
1222        }
1223
1224        assert_eq!(single_store.stats().unwrap(), batch_store.stats().unwrap());
1225    }
1226
1227    #[test]
1228    fn windows_remain_exact_across_the_u64_millisecond_boundary() {
1229        let clock = WideManualClock::new(u128::from(u64::MAX));
1230        let store = MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), clock.clone());
1231        let policy = policy("auth.login", "client", MAX_LIMIT, MAX_WINDOW);
1232        let check = Check::with_cost(&policy, subject(1), MAX_LIMIT).unwrap();
1233
1234        let first = store.check(&check).unwrap();
1235        assert!(first.is_allowed());
1236        assert_eq!(first.available(), Some(0));
1237        assert_eq!(first.replenishes_after(), Some(MAX_WINDOW));
1238
1239        let denied = store.check(&check).unwrap();
1240        assert!(denied.is_denied());
1241        assert_eq!(denied.retry_after(), Some(MAX_WINDOW));
1242
1243        clock.advance(u128::from(MAX_WINDOW_MILLIS - 1));
1244        let nearly_reset = store.check(&check).unwrap();
1245        assert!(nearly_reset.is_denied());
1246        assert_eq!(nearly_reset.retry_after(), Some(Duration::from_millis(1)));
1247
1248        clock.advance(1);
1249        let reset = store.check(&check).unwrap();
1250        assert!(reset.is_allowed());
1251        assert_eq!(reset.replenishes_after(), Some(MAX_WINDOW));
1252    }
1253
1254    #[test]
1255    fn policy_configuration_changes_use_independent_counters() {
1256        let store = MemoryStore::with_clock(
1257            MemoryStoreConfig::new(2)
1258                .unwrap()
1259                .with_shard_count(1)
1260                .unwrap(),
1261            ManualClock::default(),
1262        );
1263        let strict = policy("auth.login", "client", 1, Duration::from_secs(60));
1264        let relaxed = policy("auth.login", "client", 2, Duration::from_secs(60));
1265        let key = subject(1);
1266
1267        assert!(store.check(&Check::new(&strict, key)).unwrap().is_allowed());
1268        assert!(
1269            store
1270                .check(&Check::new(&relaxed, key))
1271                .unwrap()
1272                .is_allowed()
1273        );
1274        assert_eq!(store.stats().unwrap().entries(), 2);
1275    }
1276
1277    #[test]
1278    fn capacity_exhaustion_does_not_evict_an_active_entry() {
1279        let store = MemoryStore::with_clock(
1280            MemoryStoreConfig::new(1)
1281                .unwrap()
1282                .with_shard_count(1)
1283                .unwrap(),
1284            ManualClock::default(),
1285        );
1286        let policy = policy("auth.login", "client", 10, Duration::from_secs(60));
1287
1288        assert!(
1289            store
1290                .check(&Check::new(&policy, subject(1)))
1291                .unwrap()
1292                .is_allowed()
1293        );
1294        let denied = store.check(&Check::new(&policy, subject(2))).unwrap();
1295        assert!(!denied.is_allowed());
1296        assert_eq!(denied.retry_after(), Some(Duration::from_secs(60)));
1297        assert_eq!(store.stats().unwrap().entries(), 1);
1298    }
1299
1300    #[test]
1301    fn default_configuration_can_use_its_entire_capacity() {
1302        let store =
1303            MemoryStore::with_clock(MemoryStoreConfig::new(64).unwrap(), ManualClock::default());
1304        let policy = policy("auth.login", "client", 10, Duration::from_secs(60));
1305
1306        for byte in 0..64 {
1307            assert!(
1308                store
1309                    .check(&Check::new(&policy, subject(byte)))
1310                    .unwrap()
1311                    .is_allowed()
1312            );
1313        }
1314
1315        let denied = store.check(&Check::new(&policy, subject(64))).unwrap();
1316        assert!(denied.is_denied());
1317        assert_eq!(store.stats().unwrap().entries(), 64);
1318    }
1319
1320    #[test]
1321    fn a_cross_shard_batch_preserves_input_order_and_updates_each_shard() {
1322        let store = MemoryStore::with_clock(
1323            MemoryStoreConfig::new(4)
1324                .unwrap()
1325                .with_shard_count(2)
1326                .unwrap(),
1327            ManualClock::default(),
1328        );
1329        let policy = policy("auth.login", "client", 10, Duration::from_secs(60));
1330        let shard_zero = subjects_for_shard(&store, &policy, 0, 1)[0];
1331        let shard_one = subjects_for_shard(&store, &policy, 1, 2);
1332        let checks = [
1333            Check::with_cost(&policy, shard_one[0], 2).unwrap(),
1334            Check::with_cost(&policy, shard_zero, 3).unwrap(),
1335            Check::with_cost(&policy, shard_one[1], 4).unwrap(),
1336        ];
1337
1338        assert_eq!(
1339            store.check_all(&checks),
1340            Ok(BatchDecision::allowed(vec![
1341                Decision::allowed(10, 8, Duration::from_secs(60)),
1342                Decision::allowed(10, 7, Duration::from_secs(60)),
1343                Decision::allowed(10, 6, Duration::from_secs(60)),
1344            ]))
1345        );
1346        assert_eq!(store.shards.shard(0).lock().unwrap().used(), 1);
1347        assert_eq!(store.shards.shard(1).lock().unwrap().used(), 2);
1348    }
1349
1350    #[test]
1351    fn a_full_shard_denies_a_batch_while_another_shard_has_room() {
1352        let store = MemoryStore::with_clock(
1353            MemoryStoreConfig::new(6)
1354                .unwrap()
1355                .with_shard_count(2)
1356                .unwrap(),
1357            ManualClock::default(),
1358        );
1359        let policy = policy("auth.login", "client", 10, Duration::from_secs(60));
1360        let crowded = subjects_for_shard(&store, &policy, 0, 4);
1361        let other = subjects_for_shard(&store, &policy, 1, 1)[0];
1362
1363        for key in &crowded[..2] {
1364            assert!(
1365                store
1366                    .check(&Check::new(&policy, *key))
1367                    .unwrap()
1368                    .is_allowed()
1369            );
1370        }
1371        let checks = [
1372            Check::new(&policy, other),
1373            Check::new(&policy, crowded[2]),
1374            Check::new(&policy, crowded[3]),
1375        ];
1376
1377        assert_eq!(
1378            store.check_all(&checks),
1379            Ok(BatchDecision::denied(
1380                2,
1381                Denial::storage_capacity(Some(Duration::from_secs(60))),
1382            ))
1383        );
1384        assert_eq!(store.shards.shard(0).lock().unwrap().used(), 2);
1385        assert_eq!(store.shards.shard(1).lock().unwrap().used(), 0);
1386
1387        assert!(
1388            store
1389                .check(&Check::new(&policy, crowded[2]))
1390                .unwrap()
1391                .is_allowed()
1392        );
1393        assert!(
1394            store
1395                .check(&Check::new(&policy, other))
1396                .unwrap()
1397                .is_allowed()
1398        );
1399    }
1400
1401    #[test]
1402    fn an_unsatisfiable_per_shard_batch_returns_a_structural_error() {
1403        let store = MemoryStore::with_clock(
1404            MemoryStoreConfig::new(4)
1405                .unwrap()
1406                .with_shard_count(2)
1407                .unwrap(),
1408            ManualClock::default(),
1409        );
1410        let policy = policy("auth.login", "client", 2, Duration::from_secs(60));
1411        let keys = subjects_for_shard(&store, &policy, 0, 3);
1412        let other = subjects_for_shard(&store, &policy, 1, 1)[0];
1413        let other_check = Check::new(&policy, other);
1414        assert_eq!(
1415            store.check(&other_check),
1416            Ok(Decision::allowed(2, 1, Duration::from_secs(60)))
1417        );
1418        let checks = [
1419            other_check,
1420            Check::new(&policy, keys[0]),
1421            Check::new(&policy, keys[1]),
1422            Check::new(&policy, keys[2]),
1423        ];
1424
1425        assert_eq!(
1426            store.check_all(&checks),
1427            Err(MemoryStoreError::BatchExceedsShardCapacity {
1428                shard_index: 0,
1429                key_count: 3,
1430                capacity: 2,
1431            })
1432        );
1433        assert_eq!(store.stats().unwrap().entries(), 1);
1434        assert_eq!(
1435            store.check(&other_check),
1436            Ok(Decision::allowed(2, 0, Duration::from_secs(60)))
1437        );
1438    }
1439
1440    #[test]
1441    fn expiry_cleanup_is_bounded_and_capacity_remains_hard_bounded() {
1442        let clock = ManualClock::default();
1443        let config = MemoryStoreConfig::new(3)
1444            .unwrap()
1445            .with_shard_count(1)
1446            .unwrap()
1447            .with_max_expired_removals_per_check(1)
1448            .unwrap();
1449        let store = MemoryStore::with_clock(config, clock.clone());
1450        let policy = policy("auth.login", "client", 10, Duration::from_secs(1));
1451
1452        for byte in 1..=3 {
1453            assert!(
1454                store
1455                    .check(&Check::new(&policy, subject(byte)))
1456                    .unwrap()
1457                    .is_allowed()
1458            );
1459        }
1460        clock.advance(Duration::from_secs(1));
1461
1462        assert!(
1463            store
1464                .check(&Check::new(&policy, subject(4)))
1465                .unwrap()
1466                .is_allowed()
1467        );
1468        assert_eq!(store.stats().unwrap().entries(), 3);
1469
1470        assert!(
1471            store
1472                .check(&Check::new(&policy, subject(5)))
1473                .unwrap()
1474                .is_allowed()
1475        );
1476        assert_eq!(store.stats().unwrap().entries(), 3);
1477    }
1478
1479    #[test]
1480    fn a_cross_shard_batch_attributes_cleanup_to_each_checks_target() {
1481        let clock = ManualClock::default();
1482        let store = MemoryStore::with_clock(
1483            MemoryStoreConfig::new(8)
1484                .unwrap()
1485                .with_shard_count(2)
1486                .unwrap()
1487                .with_max_expired_removals_per_check(1)
1488                .unwrap(),
1489            clock.clone(),
1490        );
1491        let policy = policy("auth.login", "client", 10, Duration::from_secs(1));
1492        let shard_zero = subjects_for_shard(&store, &policy, 0, 6);
1493        let shard_one = subjects_for_shard(&store, &policy, 1, 5);
1494
1495        for key in shard_zero[..4].iter().chain(&shard_one[..4]) {
1496            assert!(
1497                store
1498                    .check(&Check::new(&policy, *key))
1499                    .unwrap()
1500                    .is_allowed()
1501            );
1502        }
1503        clock.advance(Duration::from_secs(1));
1504
1505        let checks = [
1506            Check::new(&policy, shard_zero[4]),
1507            Check::new(&policy, shard_one[4]),
1508            Check::new(&policy, shard_zero[5]),
1509        ];
1510        assert_eq!(
1511            store
1512                .check_all(&checks)
1513                .unwrap()
1514                .allowed_decisions()
1515                .map(<[Decision]>::len),
1516            Some(3),
1517            "the two checks targeting shard 0 need two cleanup slots"
1518        );
1519
1520        let shard = store.shards.shard(0).lock().unwrap();
1521        assert_eq!(shard.used(), 4);
1522        assert_eq!(shard.expiration_count_at_or_before(1_000), 2);
1523        drop(shard);
1524
1525        let shard = store.shards.shard(1).lock().unwrap();
1526        assert_eq!(shard.used(), 4);
1527        assert_eq!(shard.expiration_count_at_or_before(1_000), 3);
1528    }
1529
1530    #[test]
1531    fn an_atomic_batch_receives_the_cleanup_budget_for_each_check() {
1532        let clock = ManualClock::default();
1533        let config = MemoryStoreConfig::new(3)
1534            .unwrap()
1535            .with_shard_count(1)
1536            .unwrap()
1537            .with_max_expired_removals_per_check(1)
1538            .unwrap();
1539        let store = MemoryStore::with_clock(config, clock.clone());
1540        let policy = policy("auth.login", "client", 10, Duration::from_secs(1));
1541
1542        for byte in 1..=3 {
1543            assert!(
1544                store
1545                    .check(&Check::new(&policy, subject(byte)))
1546                    .unwrap()
1547                    .is_allowed()
1548            );
1549        }
1550        clock.advance(Duration::from_secs(1));
1551
1552        let checks = [4, 5, 6].map(|byte| Check::new(&policy, subject(byte)));
1553        let result = store.check_all(&checks).unwrap();
1554        assert_eq!(result.allowed_decisions().map(<[Decision]>::len), Some(3));
1555        assert_eq!(store.stats().unwrap().entries(), 3);
1556    }
1557
1558    #[test]
1559    fn auxiliary_expiry_index_remains_bounded_across_many_windows() {
1560        let clock = ManualClock::default();
1561        let store = MemoryStore::with_clock(
1562            MemoryStoreConfig::new(1)
1563                .unwrap()
1564                .with_shard_count(1)
1565                .unwrap(),
1566            clock.clone(),
1567        );
1568        let policy = policy("auth.login", "client", 1, Duration::from_millis(1));
1569        let check = Check::new(&policy, subject(1));
1570
1571        for _ in 0..1_000 {
1572            assert!(store.check(&check).unwrap().is_allowed());
1573            clock.advance(Duration::from_millis(1));
1574        }
1575
1576        let shard = store.shards.shard(0).lock().unwrap();
1577        assert_eq!(shard.used(), 1);
1578        assert_eq!(shard.expiration_count(), 1);
1579    }
1580
1581    #[test]
1582    fn targeted_expired_refresh_keeps_indexes_aligned_for_single_and_batch() {
1583        for use_batch in [false, true] {
1584            let clock = ManualClock::default();
1585            let store = MemoryStore::with_clock(
1586                MemoryStoreConfig::new(2)
1587                    .unwrap()
1588                    .with_shard_count(1)
1589                    .unwrap()
1590                    .with_max_expired_removals_per_check(1)
1591                    .unwrap(),
1592                clock.clone(),
1593            );
1594            let policy = policy("auth.login", "client", 10, Duration::from_millis(2));
1595            let earlier = Check::new(&policy, subject(1));
1596            let target = Check::new(&policy, subject(2));
1597
1598            assert!(store.check(&earlier).unwrap().is_allowed());
1599            clock.advance(Duration::from_millis(1));
1600            assert!(store.check(&target).unwrap().is_allowed());
1601            clock.advance(Duration::from_millis(2));
1602
1603            let decision = if use_batch {
1604                store
1605                    .check_all(std::slice::from_ref(&target))
1606                    .unwrap()
1607                    .try_into_single_decision()
1608                    .expect("a one-element batch returns one decision")
1609            } else {
1610                store.check(&target).unwrap()
1611            };
1612            assert_eq!(decision, Decision::allowed(10, 9, Duration::from_millis(2)));
1613
1614            let key = target.counter_key();
1615            let shard = store.shards.shard(0).lock().unwrap();
1616            assert_eq!(shard.used(), 1);
1617            assert_eq!(shard.expiration_count(), 1);
1618            assert_eq!(shard.entry(key), Some((&Entry { used: 1 }, 5)));
1619            assert!(shard.contains_expiration(key, 5));
1620        }
1621    }
1622
1623    #[test]
1624    fn a_denied_batch_does_not_consume_other_checks() {
1625        let store = MemoryStore::with_clock(
1626            MemoryStoreConfig::new(8)
1627                .unwrap()
1628                .with_shard_count(1)
1629                .unwrap(),
1630            ManualClock::default(),
1631        );
1632        let exhausted = policy("auth.login", "client", 1, Duration::from_secs(60));
1633        let untouched = policy("auth.login", "identity", 1, Duration::from_secs(60));
1634        let exhausted_check = Check::new(&exhausted, subject(1));
1635        let untouched_check = Check::new(&untouched, subject(2));
1636
1637        assert!(store.check(&exhausted_check).unwrap().is_allowed());
1638        let result = store
1639            .check_all(&[exhausted_check, untouched_check])
1640            .unwrap();
1641        assert!(result.is_enforced_denial());
1642        assert_eq!(result.denied_index(), Some(0));
1643
1644        assert!(
1645            store
1646                .check(&Check::new(&untouched, subject(2)))
1647                .unwrap()
1648                .is_allowed()
1649        );
1650    }
1651
1652    #[test]
1653    fn duplicate_keys_are_rejected_before_consumption() {
1654        let store =
1655            MemoryStore::with_clock(MemoryStoreConfig::new(8).unwrap(), ManualClock::default());
1656        let alpha = policy("auth.alpha", "client", 2, Duration::from_secs(60));
1657        let beta = policy("auth.beta", "client", 2, Duration::from_secs(60));
1658        let checks = [
1659            Check::new(&beta, subject(1)),
1660            Check::new(&beta, subject(1)),
1661            Check::new(&alpha, subject(2)),
1662            Check::new(&alpha, subject(2)),
1663        ];
1664
1665        assert_eq!(
1666            store.check_all(&checks),
1667            Err(MemoryStoreError::InvalidBatch(BatchError::DuplicateKey {
1668                first_index: 0,
1669                duplicate_index: 1,
1670            }))
1671        );
1672        assert_eq!(store.stats().unwrap().entries(), 0);
1673    }
1674
1675    #[test]
1676    fn concurrent_checks_never_over_admit() {
1677        let store = Arc::new(MemoryStore::with_clock(
1678            MemoryStoreConfig::new(8).unwrap(),
1679            ManualClock::default(),
1680        ));
1681        let policy = Arc::new(policy("auth.login", "client", 25, Duration::from_secs(60)));
1682
1683        let allowed = (0..100)
1684            .map(|_| {
1685                let store = Arc::clone(&store);
1686                let policy = Arc::clone(&policy);
1687                thread::spawn(move || {
1688                    store
1689                        .check(&Check::new(&policy, subject(1)))
1690                        .unwrap()
1691                        .is_allowed()
1692                })
1693            })
1694            .map(|thread| usize::from(thread.join().unwrap()))
1695            .sum::<usize>();
1696
1697        assert_eq!(allowed, 25);
1698    }
1699
1700    #[test]
1701    fn concurrent_cross_shard_batches_lock_consistently_and_never_over_admit() {
1702        const THREAD_COUNT: usize = 8;
1703        const CALLS_PER_THREAD: usize = 64;
1704
1705        let store = MemoryStore::with_clock(
1706            MemoryStoreConfig::new(2)
1707                .unwrap()
1708                .with_shard_count(2)
1709                .unwrap(),
1710            ManualClock::default(),
1711        );
1712        let limit = u64::try_from(THREAD_COUNT * CALLS_PER_THREAD).unwrap();
1713        let policy = policy("auth.login", "client", limit, Duration::from_secs(60));
1714        let first = subjects_for_shard(&store, &policy, 0, 1)[0];
1715        let second = subjects_for_shard(&store, &policy, 1, 1)[0];
1716        let store = Arc::new(store);
1717        let policy = Arc::new(policy);
1718        let barrier = Arc::new(Barrier::new(THREAD_COUNT));
1719        let (finished_sender, finished_receiver) = mpsc::channel();
1720
1721        let threads = (0..THREAD_COUNT)
1722            .map(|thread_index| {
1723                let store = Arc::clone(&store);
1724                let policy = Arc::clone(&policy);
1725                let barrier = Arc::clone(&barrier);
1726                let finished_sender = finished_sender.clone();
1727                thread::spawn(move || {
1728                    for call_index in 0..CALLS_PER_THREAD {
1729                        barrier.wait();
1730                        let subjects = if (thread_index + call_index) % 2 == 0 {
1731                            [first, second]
1732                        } else {
1733                            [second, first]
1734                        };
1735                        let checks = subjects.map(|subject| Check::new(policy.as_ref(), subject));
1736                        let result = store.check_all(&checks).unwrap();
1737                        assert!(
1738                            result
1739                                .allowed_decisions()
1740                                .is_some_and(|decisions| decisions.len() == checks.len()),
1741                            "every call through the configured limit must be allowed: {result:?}"
1742                        );
1743                    }
1744                    finished_sender.send(()).unwrap();
1745                })
1746            })
1747            .collect::<Vec<_>>();
1748        drop(finished_sender);
1749
1750        for _ in 0..THREAD_COUNT {
1751            finished_receiver
1752                .recv_timeout(Duration::from_secs(5))
1753                .expect("cross-shard batches must not deadlock");
1754        }
1755        for thread in threads {
1756            thread.join().unwrap();
1757        }
1758
1759        assert_eq!(store.stats().unwrap().entries(), 2);
1760        for key in [first, second] {
1761            assert_eq!(
1762                store.check(&Check::new(policy.as_ref(), key)),
1763                Ok(Decision::denied(quota(limit, Duration::from_secs(60))))
1764            );
1765        }
1766    }
1767
1768    #[test]
1769    fn a_poisoned_default_shard_remains_fail_closed() {
1770        let clock = PanicOnceClock::default();
1771        let store = MemoryStore::with_clock(
1772            MemoryStoreConfig::new(1)
1773                .unwrap()
1774                .with_shard_count(1)
1775                .unwrap(),
1776            clock.clone(),
1777        );
1778        let policy = policy("auth.login", "client", 1, Duration::from_secs(60));
1779        let exhausted = Check::new(&policy, subject(1));
1780        let new_key = Check::new(&policy, subject(2));
1781
1782        assert!(store.check(&exhausted).unwrap().is_allowed());
1783        clock.panic_once();
1784        let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
1785            let _ = store.check(&new_key);
1786        }));
1787        assert!(panic_result.is_err());
1788
1789        let poisoned = Err(MemoryStoreError::PoisonedShard { shard_index: 0 });
1790        assert_eq!(store.check(&exhausted), poisoned);
1791        assert_eq!(store.check(&new_key), poisoned);
1792        assert_eq!(store.check(&exhausted), poisoned);
1793        assert_eq!(
1794            store.stats(),
1795            Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1796        );
1797        assert_eq!(
1798            store.clear(),
1799            Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1800        );
1801    }
1802
1803    #[test]
1804    fn batch_preflight_preserves_validation_capacity_and_lock_precedence() {
1805        let clock = PanicOnceClock::default();
1806        let store = MemoryStore::with_clock(
1807            MemoryStoreConfig::new(1)
1808                .unwrap()
1809                .with_shard_count(1)
1810                .unwrap()
1811                .with_max_batch_size(2)
1812                .unwrap(),
1813            clock.clone(),
1814        );
1815        let policy = policy("auth.preflight", "client", 1, Duration::from_secs(60));
1816        let checks = [
1817            Check::new(&policy, subject(1)),
1818            Check::new(&policy, subject(2)),
1819            Check::new(&policy, subject(3)),
1820        ];
1821
1822        clock.panic_once();
1823        let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
1824            let _ = store.check(&checks[0]);
1825        }));
1826        assert!(panic_result.is_err());
1827
1828        assert_eq!(store.check_all(&[]), Ok(BatchDecision::allowed(Vec::new())));
1829        assert_eq!(
1830            store.check_all(&[checks[0], checks[0]]),
1831            Err(MemoryStoreError::InvalidBatch(BatchError::DuplicateKey {
1832                first_index: 0,
1833                duplicate_index: 1,
1834            }))
1835        );
1836        assert_eq!(
1837            store.check_all(&checks),
1838            Err(MemoryStoreError::InvalidBatch(BatchError::BatchTooLarge {
1839                actual: 3,
1840                maximum: 2,
1841            }))
1842        );
1843        assert_eq!(
1844            store.check_all(&checks[..2]),
1845            Err(MemoryStoreError::BatchExceedsShardCapacity {
1846                shard_index: 0,
1847                key_count: 2,
1848                capacity: 1,
1849            })
1850        );
1851        assert_eq!(
1852            store.check_all(&checks[..1]),
1853            Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1854        );
1855    }
1856
1857    #[test]
1858    fn failed_checks_keep_policy_metadata_but_failed_batches_remain_anonymous() {
1859        let clock = PanicOnceClock::default();
1860        let observer = Arc::new(AdmissionMetadataObserver::default());
1861        let store = MemoryStore::with_clock(
1862            MemoryStoreConfig::new(1)
1863                .unwrap()
1864                .with_shard_count(1)
1865                .unwrap(),
1866            clock.clone(),
1867        )
1868        .with_observer(observer.clone());
1869        let policy = policy(
1870            "auth.observed-failure",
1871            "client",
1872            1,
1873            Duration::from_secs(60),
1874        );
1875        let check = Check::new(&policy, subject(1));
1876
1877        clock.panic_once();
1878        let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
1879            let _ = store.check(&check);
1880        }));
1881        assert!(panic_result.is_err());
1882        assert_eq!(
1883            store.check(&check),
1884            Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1885        );
1886        assert_eq!(
1887            store.check_all(&[check]),
1888            Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1889        );
1890
1891        assert_eq!(
1892            observer.admissions.lock().unwrap().as_slice(),
1893            [
1894                RecordedAdmissionMetadata {
1895                    operation: AdmissionOperation::Check,
1896                    batch_size: 1,
1897                    has_policy_id: true,
1898                    has_scope_id: true,
1899                    has_policy_fingerprint: true,
1900                    outcome: AdmissionOutcome::Failed,
1901                    consumption: ConsumptionStatus::NotConsumed,
1902                },
1903                RecordedAdmissionMetadata {
1904                    operation: AdmissionOperation::Batch,
1905                    batch_size: 1,
1906                    has_policy_id: false,
1907                    has_scope_id: false,
1908                    has_policy_fingerprint: false,
1909                    outcome: AdmissionOutcome::Failed,
1910                    consumption: ConsumptionStatus::NotConsumed,
1911                },
1912            ]
1913        );
1914    }
1915
1916    #[test]
1917    fn explicit_recovery_resets_only_poisoned_shards_behind_an_arc() {
1918        let clock = PanicOnceClock::default();
1919        let store = Arc::new(MemoryStore::with_clock(
1920            MemoryStoreConfig::new(4)
1921                .unwrap()
1922                .with_shard_count(2)
1923                .unwrap(),
1924            clock.clone(),
1925        ));
1926        let policy = policy("auth.login", "client", 1, Duration::from_secs(60));
1927        let reset_subject = subjects_for_shard(&store, &policy, 0, 1)[0];
1928        let retained_subject = subjects_for_shard(&store, &policy, 1, 1)[0];
1929        let reset_check = Check::new(&policy, reset_subject);
1930        let retained_check = Check::new(&policy, retained_subject);
1931
1932        assert!(store.check(&reset_check).unwrap().is_allowed());
1933        assert!(store.check(&retained_check).unwrap().is_allowed());
1934        clock.panic_once();
1935        let panicked_store = Arc::clone(&store);
1936        let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(move || {
1937            let _ = panicked_store.check(&reset_check);
1938        }));
1939        assert!(panic_result.is_err());
1940
1941        assert_eq!(
1942            store.check(&reset_check),
1943            Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1944        );
1945        assert!(store.check(&retained_check).unwrap().is_denied());
1946        assert!(format!("{store:?}").contains("poisoned_shards: 1"));
1947
1948        assert_eq!(store.recover_poisoned(), 1);
1949        assert_eq!(
1950            store.recover_poisoned(),
1951            0,
1952            "recovery must be idempotent when no new panic occurs"
1953        );
1954        assert_eq!(store.stats().unwrap().entries(), 1);
1955        assert!(
1956            store.check(&reset_check).unwrap().is_allowed(),
1957            "the recovered shard starts with empty quota state"
1958        );
1959        assert!(
1960            store.check(&retained_check).unwrap().is_denied(),
1961            "healthy-shard quota state must survive recovery"
1962        );
1963        assert!(format!("{store:?}").contains("poisoned_shards: 0"));
1964    }
1965
1966    #[test]
1967    fn recovery_reopens_every_shard_poisoned_by_an_unwinding_batch() {
1968        let clock = PanicOnceClock::default();
1969        let store = Arc::new(MemoryStore::with_clock(
1970            MemoryStoreConfig::new(2)
1971                .unwrap()
1972                .with_shard_count(2)
1973                .unwrap(),
1974            clock.clone(),
1975        ));
1976        let policy = policy("auth.login", "client", 1, Duration::from_secs(60));
1977        let shard_zero = subjects_for_shard(&store, &policy, 0, 1)[0];
1978        let shard_one = subjects_for_shard(&store, &policy, 1, 1)[0];
1979        let checks = [
1980            Check::new(&policy, shard_one),
1981            Check::new(&policy, shard_zero),
1982        ];
1983
1984        clock.panic_once();
1985        let panicked_store = Arc::clone(&store);
1986        let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(move || {
1987            let _ = panicked_store.check_all(&checks);
1988        }));
1989        assert!(panic_result.is_err());
1990        assert_eq!(
1991            store.check(&checks[0]),
1992            Err(MemoryStoreError::PoisonedShard { shard_index: 1 })
1993        );
1994        assert_eq!(
1995            store.check(&checks[1]),
1996            Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1997        );
1998
1999        assert_eq!(store.recover_poisoned(), 2);
2000        assert_eq!(store.stats().unwrap().entries(), 0);
2001        assert!(
2002            store
2003                .check_all(&checks)
2004                .unwrap()
2005                .allowed_decisions()
2006                .is_some_and(|decisions| decisions.len() == 2),
2007            "all shards must be usable after one atomic recovery"
2008        );
2009    }
2010}