Skip to main content

runlimit_memory/
store.rs

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