Skip to main content

runlimit_memory/
gcra.rs

1use std::{
2    collections::{BTreeSet, HashMap},
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, CapacityObservation,
11    Check, CleanupObservation, ConsumptionStatus, CounterKey, Decision, Denial, GcraPolicy,
12    Limiter, Observation, Observer, QuotaMode, observe_safely, validate_batch,
13};
14
15use crate::{Clock, MemoryStoreConfig, MemoryStoreError, MemoryStoreStats, SystemClock};
16
17#[derive(Clone, Copy, Debug, Eq, PartialEq)]
18struct Entry {
19    tat_scaled: u128,
20    expires_at_millis: u128,
21}
22
23#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
24struct Expiration {
25    expires_at_millis: u128,
26    key: CounterKey,
27}
28
29#[derive(Clone, Copy, Debug, Eq, PartialEq)]
30struct PrehashedCounterKey(CounterKey);
31
32impl Hash for PrehashedCounterKey {
33    fn hash<H: Hasher>(&self, state: &mut H) {
34        state.write_u64(counter_key_hash(self.0));
35    }
36}
37
38#[derive(Default)]
39struct PassThroughHasher(u64);
40
41impl Hasher for PassThroughHasher {
42    fn finish(&self) -> u64 {
43        self.0
44    }
45
46    fn write(&mut self, bytes: &[u8]) {
47        for &byte in bytes {
48            self.0 = self.0.rotate_left(8) ^ u64::from(byte);
49        }
50    }
51
52    fn write_u64(&mut self, value: u64) {
53        self.0 = value;
54    }
55}
56
57type EntryMap = HashMap<PrehashedCounterKey, Entry, BuildHasherDefault<PassThroughHasher>>;
58
59#[derive(Debug)]
60struct Shard {
61    capacity: usize,
62    latest_observed_millis: u128,
63    entries: EntryMap,
64    expirations: BTreeSet<Expiration>,
65}
66
67impl Shard {
68    fn new(capacity: usize) -> Self {
69        Self {
70            capacity,
71            latest_observed_millis: 0,
72            entries: HashMap::with_hasher(BuildHasherDefault::default()),
73            expirations: BTreeSet::new(),
74        }
75    }
76
77    fn clear(&mut self) {
78        self.entries.clear();
79        self.expirations.clear();
80    }
81
82    fn prune_expired(&mut self, now_millis: u128, maximum: usize) -> usize {
83        let mut removed_count = 0;
84        for _ in 0..maximum {
85            let Some(expiration) = self.expirations.first() else {
86                break;
87            };
88            if expiration.expires_at_millis > now_millis {
89                break;
90            }
91
92            let expiration = self
93                .expirations
94                .pop_first()
95                .expect("the first expiration was present");
96            let removed = self.entries.remove(&PrehashedCounterKey(expiration.key));
97            debug_assert_eq!(
98                removed.map(|entry| entry.expires_at_millis),
99                Some(expiration.expires_at_millis),
100                "the entry and expiration indexes diverged"
101            );
102            removed_count += usize::from(removed.is_some());
103        }
104        removed_count
105    }
106
107    fn capacity_retry_after(&self, now_millis: u128) -> Option<Duration> {
108        self.expirations.first().map(|expiration| {
109            duration_from_millis(
110                expiration
111                    .expires_at_millis
112                    .saturating_sub(now_millis)
113                    .max(1),
114            )
115        })
116    }
117
118    fn evaluate(
119        &self,
120        check: &PreparedCheck,
121        now_millis: u128,
122    ) -> Result<PendingAllowance, EvaluationError> {
123        let scaled_now = now_millis
124            .checked_mul(u128::from(check.quota))
125            .ok_or(EvaluationError::Arithmetic)?;
126        let active_tat = self
127            .entries
128            .get(&PrehashedCounterKey(check.counter_key))
129            .filter(|entry| entry.expires_at_millis > now_millis)
130            .map_or(scaled_now, |entry| entry.tat_scaled.max(scaled_now));
131        let increment = u128::from(check.cost)
132            .checked_mul(u128::from(check.period_millis))
133            .ok_or(EvaluationError::Arithmetic)?;
134        let candidate = active_tat
135            .checked_add(increment)
136            .ok_or(EvaluationError::Arithmetic)?;
137        let burst_span = u128::from(check.burst_capacity)
138            .checked_mul(u128::from(check.period_millis))
139            .ok_or(EvaluationError::Arithmetic)?;
140        let ceiling = scaled_now
141            .checked_add(burst_span)
142            .ok_or(EvaluationError::Arithmetic)?;
143
144        if candidate > ceiling {
145            let retry_millis = div_ceil(candidate - ceiling, u128::from(check.quota));
146            return Err(EvaluationError::Quota(Denial::QuotaExceeded {
147                capacity: check.burst_capacity,
148                retry_after: duration_from_millis(retry_millis),
149            }));
150        }
151
152        let available = (ceiling - candidate) / u128::from(check.period_millis);
153        let replenish_millis = div_ceil(candidate - scaled_now, u128::from(check.quota));
154        let expires_at_millis = now_millis
155            .checked_add(replenish_millis)
156            .ok_or(EvaluationError::Arithmetic)?;
157
158        Ok(PendingAllowance {
159            tat_scaled: candidate,
160            expires_at_millis,
161            available: u64::try_from(available)
162                .expect("available allowance cannot exceed the u64 burst capacity"),
163            replenishes_after: duration_from_millis(replenish_millis),
164        })
165    }
166
167    fn consume(&mut self, check: &PreparedCheck, allowance: PendingAllowance) -> Decision {
168        let fresh_entry = Entry {
169            tat_scaled: allowance.tat_scaled,
170            expires_at_millis: allowance.expires_at_millis,
171        };
172        if let Some(previous) = self
173            .entries
174            .insert(PrehashedCounterKey(check.counter_key), fresh_entry)
175        {
176            let removed = self.expirations.remove(&Expiration {
177                expires_at_millis: previous.expires_at_millis,
178                key: check.counter_key,
179            });
180            debug_assert!(removed, "a replaced entry must have one expiration");
181        }
182        let inserted = self.expirations.insert(Expiration {
183            expires_at_millis: allowance.expires_at_millis,
184            key: check.counter_key,
185        });
186        debug_assert!(inserted, "an inserted entry must have one expiration");
187
188        Decision::allowed(
189            check.burst_capacity,
190            allowance.available,
191            allowance.replenishes_after,
192        )
193    }
194}
195
196#[derive(Clone, Copy, Debug)]
197enum EvaluationError {
198    Quota(Denial),
199    Arithmetic,
200}
201
202#[derive(Clone, Copy, Debug)]
203struct PendingAllowance {
204    tat_scaled: u128,
205    expires_at_millis: u128,
206    available: u64,
207    replenishes_after: Duration,
208}
209
210#[derive(Clone, Copy, Debug)]
211struct PreparedCheck {
212    input_index: usize,
213    counter_key: CounterKey,
214    shard_index: usize,
215    shard_position: usize,
216    quota: u64,
217    period_millis: u64,
218    burst_capacity: u64,
219    cost: u64,
220    quota_mode: QuotaMode,
221}
222
223impl PreparedCheck {
224    fn new(input_index: usize, check: &Check<'_, GcraPolicy>, shard_index: usize) -> Self {
225        Self {
226            input_index,
227            counter_key: check.counter_key(),
228            shard_index,
229            shard_position: 0,
230            quota: check.policy().quota(),
231            period_millis: check.policy().period_millis(),
232            burst_capacity: check.policy().burst_capacity(),
233            cost: check.cost(),
234            quota_mode: check.policy().quota_mode(),
235        }
236    }
237}
238
239#[derive(Clone, Copy, Debug)]
240struct CleanupEffect {
241    requested: usize,
242    removed: usize,
243    elapsed: Duration,
244}
245
246#[derive(Clone, Copy, Debug)]
247struct ShardEffect {
248    shard_index: usize,
249    cleanup: CleanupEffect,
250    used: usize,
251    capacity: usize,
252}
253
254#[derive(Debug)]
255struct Evaluation<T> {
256    value: T,
257    shard_effects: Vec<ShardEffect>,
258}
259
260/// A hard-bounded, process-local generic-cell-rate-algorithm store.
261///
262/// Each key occupies one constant-size entry. The store refuses to evict
263/// active entries, performs bounded cleanup per check, and preserves atomic
264/// all-or-nothing batches in caller order.
265pub struct GcraStore<C = SystemClock> {
266    config: MemoryStoreConfig,
267    clock: C,
268    shards: Box<[Mutex<Shard>]>,
269    observer: Option<Arc<dyn Observer>>,
270}
271
272impl<C> fmt::Debug for GcraStore<C> {
273    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
274        let poisoned_shards = self
275            .shards
276            .iter()
277            .filter(|shard| shard.is_poisoned())
278            .count();
279        formatter
280            .debug_struct("GcraStore")
281            .field("config", &self.config)
282            .field("has_observer", &self.observer.is_some())
283            .field("poisoned_shards", &poisoned_shards)
284            .field("shard_state", &"[REDACTED]")
285            .finish_non_exhaustive()
286    }
287}
288
289impl GcraStore<SystemClock> {
290    /// Creates a store using the system monotonic clock.
291    pub fn new(config: MemoryStoreConfig) -> Self {
292        Self::with_clock(config, SystemClock::new())
293    }
294}
295
296impl<C: Clock> GcraStore<C> {
297    /// Creates a store using a caller-supplied monotonic clock.
298    pub fn with_clock(config: MemoryStoreConfig, clock: C) -> Self {
299        let shards = (0..config.shard_count())
300            .map(|index| Mutex::new(Shard::new(config.shard_capacity(index))))
301            .collect::<Vec<_>>()
302            .into_boxed_slice();
303        Self {
304            config,
305            clock,
306            shards,
307            observer: None,
308        }
309    }
310
311    /// Returns this store with an operational observer.
312    #[must_use]
313    pub fn with_observer(mut self, observer: Arc<dyn Observer>) -> Self {
314        self.observer = Some(observer);
315        self
316    }
317
318    /// Evaluates and, when allowed, consumes one GCRA check.
319    ///
320    /// # Errors
321    ///
322    /// Fails closed when the target shard is poisoned or exact arithmetic
323    /// cannot represent the caller-supplied clock value.
324    pub fn check(&self, check: &Check<'_, GcraPolicy>) -> Result<Decision, MemoryStoreError> {
325        let started = Instant::now();
326        let result = self.check_inner(check);
327        let elapsed = started.elapsed();
328        match &result {
329            Ok(evaluation) => {
330                self.observe_shard_effects(&evaluation.shard_effects);
331                self.observe_admission(
332                    AdmissionOperation::Check,
333                    1,
334                    Some(check),
335                    decision_outcome(&evaluation.value),
336                    decision_consumption(&evaluation.value),
337                    elapsed,
338                );
339            }
340            Err(_) => self.observe_admission(
341                AdmissionOperation::Check,
342                1,
343                Some(check),
344                AdmissionOutcome::Failed,
345                ConsumptionStatus::NotConsumed,
346                elapsed,
347            ),
348        }
349        result.map(|evaluation| evaluation.value)
350    }
351
352    fn check_inner(
353        &self,
354        check: &Check<'_, GcraPolicy>,
355    ) -> Result<Evaluation<Decision>, MemoryStoreError> {
356        let counter_key = check.counter_key();
357        let shard_index = self.shard_index(&counter_key);
358        let prepared = PreparedCheck::new(0, check, shard_index);
359        let mut shard = self.lock_shard(shard_index)?;
360        let observed_millis = self.clock.now().as_millis();
361        let now_millis = observed_millis.max(shard.latest_observed_millis);
362        let evaluated = match shard.evaluate(&prepared, now_millis) {
363            Err(EvaluationError::Arithmetic) => {
364                return Err(MemoryStoreError::ArithmeticOverflow);
365            }
366            result => result,
367        };
368        shard.latest_observed_millis = now_millis;
369        let cleanup_requested = self.config.max_expired_removals_per_check();
370        let cleanup_started = Instant::now();
371        let cleanup_removed = shard.prune_expired(now_millis, cleanup_requested);
372        let cleanup_elapsed = cleanup_started.elapsed();
373
374        let decision = match evaluated {
375            Ok(allowance) => {
376                if !shard
377                    .entries
378                    .contains_key(&PrehashedCounterKey(counter_key))
379                    && shard.entries.len() >= shard.capacity
380                {
381                    Decision::denied(Denial::StorageCapacity {
382                        retry_after: shard.capacity_retry_after(now_millis),
383                    })
384                } else {
385                    shard.consume(&prepared, allowance)
386                }
387            }
388            Err(EvaluationError::Quota(denial)) => {
389                if prepared.quota_mode == QuotaMode::Shadow {
390                    Decision::shadow_denied(denial)
391                } else {
392                    Decision::denied(denial)
393                }
394            }
395            Err(EvaluationError::Arithmetic) => unreachable!("arithmetic was preflighted"),
396        };
397
398        Ok(Evaluation {
399            value: decision,
400            shard_effects: vec![ShardEffect {
401                shard_index,
402                cleanup: CleanupEffect {
403                    requested: cleanup_requested,
404                    removed: cleanup_removed,
405                    elapsed: cleanup_elapsed,
406                },
407                used: shard.entries.len(),
408                capacity: shard.capacity,
409            }],
410        })
411    }
412
413    /// Evaluates an atomic batch of GCRA checks.
414    ///
415    /// Allowed decisions preserve input order. A denied or shadow-denied batch
416    /// consumes no quota.
417    ///
418    /// # Errors
419    ///
420    /// Fails closed for invalid batches, poisoned shards, an unsatisfiable
421    /// per-shard batch, or arithmetic overflow.
422    #[allow(clippy::too_many_lines)]
423    pub fn check_all(
424        &self,
425        checks: &[Check<'_, GcraPolicy>],
426    ) -> Result<BatchDecision, MemoryStoreError> {
427        let started = Instant::now();
428        let result = self.check_all_inner(checks);
429        let elapsed = started.elapsed();
430        match &result {
431            Ok(evaluation) => {
432                self.observe_shard_effects(&evaluation.shard_effects);
433                let relevant_check = batch_relevant_check(checks, &evaluation.value);
434                self.observe_admission(
435                    AdmissionOperation::Batch,
436                    checks.len(),
437                    relevant_check,
438                    batch_outcome(&evaluation.value),
439                    batch_consumption(&evaluation.value, checks.is_empty()),
440                    elapsed,
441                );
442            }
443            Err(_) => self.observe_admission(
444                AdmissionOperation::Batch,
445                checks.len(),
446                None,
447                AdmissionOutcome::Failed,
448                ConsumptionStatus::NotConsumed,
449                elapsed,
450            ),
451        }
452        result.map(|evaluation| evaluation.value)
453    }
454
455    #[allow(clippy::too_many_lines)]
456    fn check_all_inner(
457        &self,
458        checks: &[Check<'_, GcraPolicy>],
459    ) -> Result<Evaluation<BatchDecision>, MemoryStoreError> {
460        validate_batch(checks, self.config.max_batch_size())?;
461        if checks.is_empty() {
462            return Ok(Evaluation {
463                value: BatchDecision::Allowed(Vec::new()),
464                shard_effects: Vec::new(),
465            });
466        }
467
468        let mut prepared = Vec::with_capacity(checks.len());
469        for (input_index, check) in checks.iter().enumerate() {
470            let counter_key = check.counter_key();
471            prepared.push(PreparedCheck::new(
472                input_index,
473                check,
474                self.shard_index(&counter_key),
475            ));
476        }
477        let mut shard_indexes = prepared
478            .iter()
479            .map(|check| check.shard_index)
480            .collect::<Vec<_>>();
481        shard_indexes.sort_unstable();
482        shard_indexes.dedup();
483        for check in &mut prepared {
484            check.shard_position =
485                shard_indexes.partition_point(|index| *index < check.shard_index);
486        }
487
488        let mut checks_per_shard = vec![0_usize; shard_indexes.len()];
489        for check in &prepared {
490            checks_per_shard[check.shard_position] += 1;
491        }
492        for (&shard_index, &key_count) in shard_indexes.iter().zip(&checks_per_shard) {
493            let capacity = self.config.shard_capacity(shard_index);
494            if key_count > capacity {
495                return Err(MemoryStoreError::BatchExceedsShardCapacity {
496                    shard_index,
497                    key_count,
498                    capacity,
499                });
500            }
501        }
502
503        let mut locked_shards = self.lock_shards(&shard_indexes)?;
504        let observed_millis = self.clock.now().as_millis();
505        let now_millis = locked_shards
506            .iter()
507            .map(|(_, shard)| shard.latest_observed_millis)
508            .fold(observed_millis, u128::max);
509        let mut evaluations = Vec::with_capacity(prepared.len());
510        for check in &prepared {
511            match locked_shards[check.shard_position]
512                .1
513                .evaluate(check, now_millis)
514            {
515                Err(EvaluationError::Arithmetic) => {
516                    return Err(MemoryStoreError::ArithmeticOverflow);
517                }
518                evaluation => evaluations.push(evaluation),
519            }
520        }
521        let mut cleanup_effects = Vec::with_capacity(locked_shards.len());
522        for ((_, shard), &check_count) in locked_shards.iter_mut().zip(&checks_per_shard) {
523            shard.latest_observed_millis = now_millis;
524            let requested = self
525                .config
526                .max_expired_removals_per_check()
527                .saturating_mul(check_count);
528            let cleanup_started = Instant::now();
529            let removed = shard.prune_expired(now_millis, requested);
530            cleanup_effects.push(CleanupEffect {
531                requested,
532                removed,
533                elapsed: cleanup_started.elapsed(),
534            });
535        }
536
537        let mut pending_insertions = vec![0_usize; locked_shards.len()];
538        let mut allowances = Vec::with_capacity(prepared.len());
539        for (check, evaluation) in prepared.iter().zip(evaluations) {
540            let shard = &locked_shards[check.shard_position].1;
541            let allowance = match evaluation {
542                Ok(allowance) => allowance,
543                Err(EvaluationError::Quota(denial)) => {
544                    let value = if check.quota_mode == QuotaMode::Shadow {
545                        BatchDecision::ShadowDenied {
546                            index: check.input_index,
547                            denial,
548                        }
549                    } else {
550                        BatchDecision::Denied {
551                            index: check.input_index,
552                            denial,
553                        }
554                    };
555                    return Ok(Evaluation {
556                        value,
557                        shard_effects: collect_shard_effects(&locked_shards, &cleanup_effects),
558                    });
559                }
560                Err(EvaluationError::Arithmetic) => unreachable!("arithmetic was preflighted"),
561            };
562
563            if !shard
564                .entries
565                .contains_key(&PrehashedCounterKey(check.counter_key))
566            {
567                let projected_len = shard.entries.len() + pending_insertions[check.shard_position];
568                if projected_len >= shard.capacity {
569                    return Ok(Evaluation {
570                        value: BatchDecision::Denied {
571                            index: check.input_index,
572                            denial: Denial::StorageCapacity {
573                                retry_after: shard.capacity_retry_after(now_millis),
574                            },
575                        },
576                        shard_effects: collect_shard_effects(&locked_shards, &cleanup_effects),
577                    });
578                }
579                pending_insertions[check.shard_position] += 1;
580            }
581            allowances.push(allowance);
582        }
583
584        let mut decisions = Vec::with_capacity(prepared.len());
585        for (check, allowance) in prepared.iter().zip(allowances) {
586            decisions.push(
587                locked_shards[check.shard_position]
588                    .1
589                    .consume(check, allowance),
590            );
591        }
592        Ok(Evaluation {
593            value: BatchDecision::Allowed(decisions),
594            shard_effects: collect_shard_effects(&locked_shards, &cleanup_effects),
595        })
596    }
597
598    /// Returns current bounded storage use.
599    ///
600    /// # Errors
601    ///
602    /// Returns an error if any shard is poisoned.
603    pub fn stats(&self) -> Result<MemoryStoreStats, MemoryStoreError> {
604        let indexes = (0..self.shards.len()).collect::<Vec<_>>();
605        let locked = self.lock_shards(&indexes)?;
606        Ok(MemoryStoreStats::from_parts(
607            locked.iter().map(|(_, shard)| shard.entries.len()).sum(),
608            self.config.max_keys(),
609            self.config.shard_count(),
610        ))
611    }
612
613    /// Removes every stored counter.
614    ///
615    /// # Errors
616    ///
617    /// Returns an error if any shard is poisoned.
618    pub fn clear(&self) -> Result<(), MemoryStoreError> {
619        let indexes = (0..self.shards.len()).collect::<Vec<_>>();
620        let mut locked = self.lock_shards(&indexes)?;
621        for (_, shard) in &mut locked {
622            shard.clear();
623        }
624        Ok(())
625    }
626
627    /// Rebuilds poisoned shards by discarding their untrusted counter state.
628    pub fn recover_poisoned(&self) -> usize {
629        let mut locked = Vec::with_capacity(self.shards.len());
630        for (index, mutex) in self.shards.iter().enumerate() {
631            match mutex.lock() {
632                Ok(shard) => locked.push((index, mutex, shard, false)),
633                Err(poisoned) => locked.push((index, mutex, poisoned.into_inner(), true)),
634            }
635        }
636        let mut recovered = 0;
637        for (index, mutex, shard, poisoned) in &mut locked {
638            if *poisoned {
639                **shard = Shard::new(self.config.shard_capacity(*index));
640                mutex.clear_poison();
641                recovered += 1;
642            }
643        }
644        recovered
645    }
646
647    fn observe_shard_effects(&self, effects: &[ShardEffect]) {
648        let Some(observer) = &self.observer else {
649            return;
650        };
651        for effect in effects {
652            observe_safely(
653                observer.as_ref(),
654                &Observation::Cleanup(CleanupObservation::new(
655                    effect.cleanup.requested,
656                    Some(usize_to_u64(effect.cleanup.removed)),
657                    effect.cleanup.elapsed,
658                    ConsumptionStatus::Consumed,
659                )),
660            );
661            observe_safely(
662                observer.as_ref(),
663                &Observation::Capacity(CapacityObservation::new(
664                    usize_to_u64(effect.used),
665                    usize_to_u64(effect.capacity),
666                    Some(effect.shard_index),
667                )),
668            );
669        }
670    }
671
672    #[allow(clippy::too_many_arguments)]
673    fn observe_admission(
674        &self,
675        operation: AdmissionOperation,
676        batch_size: usize,
677        check: Option<&Check<'_, GcraPolicy>>,
678        outcome: AdmissionOutcome,
679        consumption: ConsumptionStatus,
680        elapsed: Duration,
681    ) {
682        let Some(observer) = &self.observer else {
683            return;
684        };
685        let (policy_id, scope_id) = check.map_or((None, None), |check| {
686            (Some(check.policy().id()), Some(check.policy().scope()))
687        });
688        observe_safely(
689            observer.as_ref(),
690            &Observation::Admission(AdmissionObservation::new(
691                operation,
692                batch_size,
693                policy_id,
694                scope_id,
695                outcome,
696                consumption,
697                elapsed,
698            )),
699        );
700    }
701
702    fn shard_index(&self, key: &CounterKey) -> usize {
703        #[allow(clippy::cast_possible_truncation)]
704        let hash = counter_key_hash(*key) as usize;
705        hash % self.shards.len()
706    }
707
708    fn lock_shard(&self, index: usize) -> Result<MutexGuard<'_, Shard>, MemoryStoreError> {
709        self.shards[index]
710            .lock()
711            .map_err(|_| MemoryStoreError::PoisonedShard { shard_index: index })
712    }
713
714    fn lock_shards<'a>(
715        &'a self,
716        indexes: &[usize],
717    ) -> Result<Vec<(usize, MutexGuard<'a, Shard>)>, MemoryStoreError> {
718        let mut locked = Vec::with_capacity(indexes.len());
719        for &index in indexes {
720            locked.push((index, self.lock_shard(index)?));
721        }
722        Ok(locked)
723    }
724}
725
726fn collect_shard_effects(
727    locked_shards: &[(usize, MutexGuard<'_, Shard>)],
728    cleanup_effects: &[CleanupEffect],
729) -> Vec<ShardEffect> {
730    debug_assert_eq!(locked_shards.len(), cleanup_effects.len());
731    locked_shards
732        .iter()
733        .zip(cleanup_effects)
734        .map(|((shard_index, shard), cleanup)| ShardEffect {
735            shard_index: *shard_index,
736            cleanup: *cleanup,
737            used: shard.entries.len(),
738            capacity: shard.capacity,
739        })
740        .collect()
741}
742
743fn decision_outcome(decision: &Decision) -> AdmissionOutcome {
744    if !decision.would_deny() {
745        return AdmissionOutcome::Allowed;
746    }
747    if decision.is_shadow_denied() {
748        return AdmissionOutcome::ShadowDenied;
749    }
750    match decision.denial() {
751        Some(Denial::QuotaExceeded { .. }) => AdmissionOutcome::QuotaDenied,
752        Some(Denial::StorageCapacity { .. }) => AdmissionOutcome::CapacityDenied,
753        _ => AdmissionOutcome::Failed,
754    }
755}
756
757fn decision_consumption(decision: &Decision) -> ConsumptionStatus {
758    if decision.would_deny() {
759        ConsumptionStatus::NotConsumed
760    } else {
761        ConsumptionStatus::Consumed
762    }
763}
764
765fn batch_outcome(decision: &BatchDecision) -> AdmissionOutcome {
766    match decision {
767        BatchDecision::Allowed(_) => AdmissionOutcome::Allowed,
768        BatchDecision::ShadowDenied { .. } => AdmissionOutcome::ShadowDenied,
769        BatchDecision::Denied {
770            denial: Denial::QuotaExceeded { .. },
771            ..
772        } => AdmissionOutcome::QuotaDenied,
773        BatchDecision::Denied {
774            denial: Denial::StorageCapacity { .. },
775            ..
776        } => AdmissionOutcome::CapacityDenied,
777        _ => AdmissionOutcome::Failed,
778    }
779}
780
781fn batch_consumption(decision: &BatchDecision, empty: bool) -> ConsumptionStatus {
782    if matches!(decision, BatchDecision::Allowed(_)) && !empty {
783        ConsumptionStatus::Consumed
784    } else {
785        ConsumptionStatus::NotConsumed
786    }
787}
788
789fn batch_relevant_check<'checks, 'policy>(
790    checks: &'checks [Check<'policy, GcraPolicy>],
791    decision: &BatchDecision,
792) -> Option<&'checks Check<'policy, GcraPolicy>> {
793    match decision {
794        BatchDecision::Allowed(decisions) if decisions.len() == 1 => checks.first(),
795        BatchDecision::Denied { index, .. } | BatchDecision::ShadowDenied { index, .. } => {
796            checks.get(*index)
797        }
798        _ => None,
799    }
800}
801
802fn counter_key_hash(key: CounterKey) -> u64 {
803    leading_u64(key.subject().as_bytes())
804        ^ leading_u64(key.fingerprint().as_bytes()).rotate_left(32)
805}
806
807const fn leading_u64(bytes: &[u8; 32]) -> u64 {
808    u64::from_le_bytes([
809        bytes[0], bytes[1], bytes[2], bytes[3], bytes[4], bytes[5], bytes[6], bytes[7],
810    ])
811}
812
813const fn div_ceil(numerator: u128, denominator: u128) -> u128 {
814    numerator / denominator
815        + if numerator.is_multiple_of(denominator) {
816            0
817        } else {
818            1
819        }
820}
821
822fn duration_from_millis(millis: u128) -> Duration {
823    Duration::from_millis(
824        u64::try_from(millis)
825            .expect("GCRA policy validation bounds every reported duration to u64"),
826    )
827}
828
829fn usize_to_u64(value: usize) -> u64 {
830    u64::try_from(value).unwrap_or(u64::MAX)
831}
832
833impl<C: Clock> Limiter for GcraStore<C> {
834    type Policy = GcraPolicy;
835    type Error = MemoryStoreError;
836
837    async fn check(&self, check: &Check<'_, Self::Policy>) -> Result<Decision, Self::Error> {
838        GcraStore::check(self, check)
839    }
840
841    async fn check_all(
842        &self,
843        checks: &[Check<'_, Self::Policy>],
844    ) -> Result<BatchDecision, Self::Error> {
845        GcraStore::check_all(self, checks)
846    }
847}
848
849#[cfg(test)]
850mod tests {
851    use std::{
852        sync::{
853            Arc, Barrier, Mutex,
854            atomic::{AtomicBool, AtomicU64, Ordering},
855        },
856        thread,
857        time::Duration,
858    };
859
860    use runlimit_core::{
861        AdmissionOutcome, BatchDecision, Check, ConsumptionStatus, Decision, Denial, GcraPolicy,
862        MAX_LIMIT, Observation, Observer, PolicyId, QuotaMode, ScopeId, SubjectKey,
863    };
864
865    use super::GcraStore;
866    use crate::{Clock, MemoryStoreConfig, MemoryStoreError};
867
868    #[derive(Clone, Default)]
869    struct ManualClock {
870        millis: Arc<AtomicU64>,
871    }
872
873    impl ManualClock {
874        fn advance(&self, duration: Duration) {
875            self.millis.fetch_add(
876                u64::try_from(duration.as_millis()).unwrap(),
877                Ordering::Relaxed,
878            );
879        }
880
881        fn set(&self, duration: Duration) {
882            self.millis.store(
883                u64::try_from(duration.as_millis()).unwrap(),
884                Ordering::Relaxed,
885            );
886        }
887    }
888
889    impl Clock for ManualClock {
890        fn now(&self) -> Duration {
891            Duration::from_millis(self.millis.load(Ordering::Relaxed))
892        }
893    }
894
895    #[derive(Clone, Copy)]
896    struct MaximumClock;
897
898    impl Clock for MaximumClock {
899        fn now(&self) -> Duration {
900            Duration::new(u64::MAX, 999_999_999)
901        }
902    }
903
904    #[derive(Clone, Default)]
905    struct SwitchableExtremeClock {
906        extreme: Arc<AtomicBool>,
907    }
908
909    impl SwitchableExtremeClock {
910        fn use_extreme_time(&self) {
911            self.extreme.store(true, Ordering::Relaxed);
912        }
913    }
914
915    impl Clock for SwitchableExtremeClock {
916        fn now(&self) -> Duration {
917            if self.extreme.load(Ordering::Relaxed) {
918                Duration::new(u64::MAX, 999_999_999)
919            } else {
920                Duration::ZERO
921            }
922        }
923    }
924
925    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
926    enum RecordedObservation {
927        Admission {
928            outcome: AdmissionOutcome,
929            consumption: ConsumptionStatus,
930        },
931        Cleanup {
932            removed: Option<u64>,
933        },
934        Capacity {
935            used: u64,
936            capacity: u64,
937        },
938    }
939
940    #[derive(Default)]
941    struct RecordingObserver {
942        observations: Mutex<Vec<RecordedObservation>>,
943    }
944
945    impl RecordingObserver {
946        fn take(&self) -> Vec<RecordedObservation> {
947            std::mem::take(
948                &mut *self
949                    .observations
950                    .lock()
951                    .expect("recording observer mutex remains healthy"),
952            )
953        }
954    }
955
956    impl Observer for RecordingObserver {
957        fn observe(&self, observation: &Observation<'_>) {
958            let recorded = match observation {
959                Observation::Admission(admission) => RecordedObservation::Admission {
960                    outcome: admission.outcome(),
961                    consumption: admission.consumption(),
962                },
963                Observation::Cleanup(cleanup) => RecordedObservation::Cleanup {
964                    removed: cleanup.removed(),
965                },
966                Observation::Capacity(capacity) => RecordedObservation::Capacity {
967                    used: capacity.used(),
968                    capacity: capacity.capacity(),
969                },
970                _ => return,
971            };
972            self.observations
973                .lock()
974                .expect("recording observer mutex remains healthy")
975                .push(recorded);
976        }
977    }
978
979    #[derive(Clone, Copy, Debug)]
980    struct ReferenceBucket {
981        quota: u128,
982        period_millis: u128,
983        capacity: u64,
984        tokens_scaled: u128,
985        last_millis: u64,
986    }
987
988    impl ReferenceBucket {
989        fn new(quota: u64, period_millis: u64, capacity: u64) -> Self {
990            Self {
991                quota: u128::from(quota),
992                period_millis: u128::from(period_millis),
993                capacity,
994                tokens_scaled: u128::from(capacity) * u128::from(period_millis),
995                last_millis: 0,
996            }
997        }
998
999        fn check(&mut self, now_millis: u64, cost: u64) -> Decision {
1000            assert!(now_millis >= self.last_millis);
1001            let maximum = u128::from(self.capacity) * self.period_millis;
1002            let elapsed = u128::from(now_millis - self.last_millis);
1003            self.tokens_scaled = maximum.min(self.tokens_scaled + elapsed * self.quota);
1004            self.last_millis = now_millis;
1005
1006            let requested = u128::from(cost) * self.period_millis;
1007            if requested > self.tokens_scaled {
1008                return Decision::denied(Denial::QuotaExceeded {
1009                    capacity: self.capacity,
1010                    retry_after: reference_duration(reference_div_ceil(
1011                        requested - self.tokens_scaled,
1012                        self.quota,
1013                    )),
1014                });
1015            }
1016
1017            self.tokens_scaled -= requested;
1018            Decision::allowed(
1019                self.capacity,
1020                u64::try_from(self.tokens_scaled / self.period_millis)
1021                    .expect("reference availability fits the configured capacity"),
1022                reference_duration(reference_div_ceil(maximum - self.tokens_scaled, self.quota)),
1023            )
1024        }
1025    }
1026
1027    fn reference_div_ceil(numerator: u128, denominator: u128) -> u128 {
1028        numerator.div_ceil(denominator)
1029    }
1030
1031    fn reference_duration(millis: u128) -> Duration {
1032        Duration::from_millis(
1033            u64::try_from(millis).expect("small reference-model durations fit in u64"),
1034        )
1035    }
1036
1037    fn policy(id: &str, quota: u64, period: Duration, burst_capacity: u64) -> GcraPolicy {
1038        GcraPolicy::new(
1039            PolicyId::new(id).unwrap(),
1040            ScopeId::new("client").unwrap(),
1041            quota,
1042            period,
1043            burst_capacity,
1044        )
1045        .unwrap()
1046    }
1047
1048    fn subject(byte: u8) -> SubjectKey {
1049        SubjectKey::from_digest([byte; 32])
1050    }
1051
1052    #[test]
1053    fn matches_rational_token_bucket_reference_across_small_parameter_space() {
1054        for quota in 1_u64..=5 {
1055            for period_millis in 1_u64..=10 {
1056                for capacity in 1_u64..=5 {
1057                    let clock = ManualClock::default();
1058                    let store =
1059                        GcraStore::with_clock(MemoryStoreConfig::new(1).unwrap(), clock.clone());
1060                    let id = format!("reference.{quota}.{period_millis}.{capacity}");
1061                    let policy = policy(&id, quota, Duration::from_millis(period_millis), capacity);
1062                    let mut reference = ReferenceBucket::new(quota, period_millis, capacity);
1063                    let mut now_millis = 0_u64;
1064
1065                    for step in 0_u64..40 {
1066                        now_millis += match step % 5 {
1067                            0 | 2 => 0,
1068                            1 => 1,
1069                            3 => 2,
1070                            _ => 3,
1071                        };
1072                        clock.set(Duration::from_millis(now_millis));
1073                        let cost = 1 + (step * 7 + quota + period_millis) % capacity;
1074                        let expected = reference.check(now_millis, cost);
1075                        let actual = store
1076                            .check(&Check::with_cost(&policy, subject(1), cost).unwrap())
1077                            .unwrap();
1078
1079                        assert_eq!(
1080                            actual, expected,
1081                            "quota={quota}, period={period_millis}ms, capacity={capacity}, \
1082                             step={step}, now={now_millis}ms, cost={cost}"
1083                        );
1084                    }
1085                }
1086            }
1087        }
1088    }
1089
1090    #[test]
1091    fn quota_three_per_ten_millis_rounds_fractional_boundaries_up() {
1092        let clock = ManualClock::default();
1093        let store = GcraStore::with_clock(MemoryStoreConfig::new(1).unwrap(), clock.clone());
1094        let policy = policy("api.fractional", 3, Duration::from_millis(10), 4);
1095        let subject = subject(1);
1096
1097        assert_eq!(
1098            store.check(&Check::with_cost(&policy, subject, 4).unwrap()),
1099            Ok(Decision::allowed(4, 0, Duration::from_millis(14)))
1100        );
1101        clock.set(Duration::from_millis(3));
1102        assert_eq!(
1103            store.check(&Check::new(&policy, subject)),
1104            Ok(Decision::denied(Denial::QuotaExceeded {
1105                capacity: 4,
1106                retry_after: Duration::from_millis(1),
1107            }))
1108        );
1109        clock.set(Duration::from_millis(4));
1110        assert_eq!(
1111            store.check(&Check::new(&policy, subject)),
1112            Ok(Decision::allowed(4, 0, Duration::from_millis(13)))
1113        );
1114    }
1115
1116    #[test]
1117    fn quota_above_period_milliseconds_replenishes_multiple_units_per_tick() {
1118        let clock = ManualClock::default();
1119        let store = GcraStore::with_clock(MemoryStoreConfig::new(1).unwrap(), clock.clone());
1120        let policy = policy("api.fast", 10, Duration::from_millis(1), 12);
1121        let subject = subject(1);
1122
1123        assert_eq!(
1124            store.check(&Check::with_cost(&policy, subject, 12).unwrap()),
1125            Ok(Decision::allowed(12, 0, Duration::from_millis(2)))
1126        );
1127        assert_eq!(
1128            store.check(&Check::new(&policy, subject)),
1129            Ok(Decision::denied(Denial::QuotaExceeded {
1130                capacity: 12,
1131                retry_after: Duration::from_millis(1),
1132            }))
1133        );
1134        clock.set(Duration::from_millis(1));
1135        assert_eq!(
1136            store.check(&Check::with_cost(&policy, subject, 10).unwrap()),
1137            Ok(Decision::allowed(12, 0, Duration::from_millis(2)))
1138        );
1139    }
1140
1141    #[test]
1142    fn weighted_burst_refills_at_exact_integer_boundaries() {
1143        let clock = ManualClock::default();
1144        let store = GcraStore::with_clock(MemoryStoreConfig::new(8).unwrap(), clock.clone());
1145        let policy = policy("api.read", 2, Duration::from_secs(1), 4);
1146        let check = Check::with_cost(&policy, subject(1), 3).unwrap();
1147
1148        assert_eq!(
1149            store.check(&check),
1150            Ok(Decision::allowed(4, 1, Duration::from_millis(1_500)))
1151        );
1152        assert_eq!(
1153            store.check(&Check::new(&policy, subject(1))),
1154            Ok(Decision::allowed(4, 0, Duration::from_secs(2)))
1155        );
1156        assert_eq!(
1157            store.check(&Check::new(&policy, subject(1))),
1158            Ok(Decision::denied(Denial::QuotaExceeded {
1159                capacity: 4,
1160                retry_after: Duration::from_millis(500),
1161            }))
1162        );
1163
1164        clock.advance(Duration::from_millis(499));
1165        assert_eq!(
1166            store.check(&Check::new(&policy, subject(1))),
1167            Ok(Decision::denied(Denial::QuotaExceeded {
1168                capacity: 4,
1169                retry_after: Duration::from_millis(1),
1170            }))
1171        );
1172        clock.advance(Duration::from_millis(1));
1173        assert_eq!(
1174            store.check(&Check::new(&policy, subject(1))),
1175            Ok(Decision::allowed(4, 0, Duration::from_secs(2)))
1176        );
1177
1178        clock.advance(Duration::from_secs(2));
1179        assert_eq!(
1180            store.check(&Check::new(&policy, subject(1))),
1181            Ok(Decision::allowed(4, 3, Duration::from_millis(500)))
1182        );
1183    }
1184
1185    #[test]
1186    fn regressing_clocks_cannot_refill_quota_early() {
1187        let clock = ManualClock::default();
1188        clock.set(Duration::from_secs(10));
1189        let store = GcraStore::with_clock(MemoryStoreConfig::new(2).unwrap(), clock.clone());
1190        let policy = policy("api.write", 1, Duration::from_secs(1), 1);
1191        let check = Check::new(&policy, subject(1));
1192
1193        assert!(store.check(&check).unwrap().is_allowed());
1194        clock.set(Duration::from_secs(1));
1195        assert_eq!(
1196            store.check(&check),
1197            Ok(Decision::denied(Denial::QuotaExceeded {
1198                capacity: 1,
1199                retry_after: Duration::from_secs(1),
1200            }))
1201        );
1202    }
1203
1204    #[test]
1205    fn bounded_expiry_cleanup_releases_hard_capacity() {
1206        let clock = ManualClock::default();
1207        let config = MemoryStoreConfig::new(3)
1208            .unwrap()
1209            .with_max_expired_removals_per_check(1)
1210            .unwrap();
1211        let store = GcraStore::with_clock(config, clock.clone());
1212        let policy = policy("api.read", 1, Duration::from_millis(10), 1);
1213
1214        for byte in 1..=3 {
1215            assert!(
1216                store
1217                    .check(&Check::new(&policy, subject(byte)))
1218                    .unwrap()
1219                    .is_allowed()
1220            );
1221        }
1222        assert!(
1223            store
1224                .check(&Check::new(&policy, subject(4)))
1225                .unwrap()
1226                .is_denied()
1227        );
1228
1229        clock.advance(Duration::from_millis(10));
1230        assert!(
1231            store
1232                .check(&Check::new(&policy, subject(4)))
1233                .unwrap()
1234                .is_allowed()
1235        );
1236        assert_eq!(store.stats().unwrap().entries(), 3);
1237    }
1238
1239    #[test]
1240    fn concurrent_same_key_checks_consume_exactly_one_burst() {
1241        const ATTEMPTS: usize = 32;
1242        const BURST: usize = 7;
1243
1244        let store =
1245            GcraStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default());
1246        let policy = policy(
1247            "api.concurrent",
1248            1,
1249            Duration::from_secs(60),
1250            u64::try_from(BURST).unwrap(),
1251        );
1252        let check = Check::new(&policy, subject(1));
1253        let barrier = Arc::new(Barrier::new(ATTEMPTS + 1));
1254
1255        let decisions = thread::scope(|scope| {
1256            let mut handles = Vec::with_capacity(ATTEMPTS);
1257            let store_ref = &store;
1258            for _ in 0..ATTEMPTS {
1259                let barrier = Arc::clone(&barrier);
1260                handles.push(scope.spawn(move || {
1261                    barrier.wait();
1262                    store_ref.check(&check).unwrap()
1263                }));
1264            }
1265            barrier.wait();
1266            handles
1267                .into_iter()
1268                .map(|handle| handle.join().expect("admission thread does not panic"))
1269                .collect::<Vec<_>>()
1270        });
1271
1272        assert_eq!(
1273            decisions
1274                .iter()
1275                .filter(|decision| !decision.would_deny())
1276                .count(),
1277            BURST
1278        );
1279        assert_eq!(
1280            decisions
1281                .iter()
1282                .filter(|decision| {
1283                    matches!(decision.denial(), Some(Denial::QuotaExceeded { .. }))
1284                })
1285                .count(),
1286            ATTEMPTS - BURST
1287        );
1288        assert_eq!(store.stats().unwrap().entries(), 1);
1289    }
1290
1291    #[test]
1292    fn allowed_batches_return_exact_decisions_in_input_order() {
1293        let store =
1294            GcraStore::with_clock(MemoryStoreConfig::new(2).unwrap(), ManualClock::default());
1295        let slow = policy("api.slow", 1, Duration::from_millis(10), 3);
1296        let fast = policy("api.fast", 4, Duration::from_millis(10), 5);
1297        let checks = [
1298            Check::with_cost(&fast, subject(1), 3).unwrap(),
1299            Check::with_cost(&slow, subject(1), 2).unwrap(),
1300        ];
1301
1302        assert_eq!(
1303            store.check_all(&checks),
1304            Ok(BatchDecision::Allowed(vec![
1305                Decision::allowed(5, 2, Duration::from_millis(8)),
1306                Decision::allowed(3, 1, Duration::from_millis(20)),
1307            ]))
1308        );
1309    }
1310
1311    #[test]
1312    fn enforced_quota_denial_rolls_back_earlier_batch_members() {
1313        let store =
1314            GcraStore::with_clock(MemoryStoreConfig::new(3).unwrap(), ManualClock::default());
1315        let policy = policy("api.quota-rollback", 1, Duration::from_millis(100), 1);
1316        let exhausted = Check::new(&policy, subject(1));
1317        let earlier = Check::new(&policy, subject(2));
1318        assert!(store.check(&exhausted).unwrap().is_allowed());
1319
1320        assert!(matches!(
1321            store.check_all(&[earlier, exhausted]).unwrap(),
1322            BatchDecision::Denied {
1323                index: 1,
1324                denial: Denial::QuotaExceeded { .. },
1325            }
1326        ));
1327        assert!(
1328            store.check(&earlier).unwrap().is_allowed(),
1329            "a quota-denied batch must not consume an earlier member"
1330        );
1331    }
1332
1333    #[test]
1334    fn storage_capacity_denial_rolls_back_earlier_batch_members() {
1335        let store =
1336            GcraStore::with_clock(MemoryStoreConfig::new(2).unwrap(), ManualClock::default());
1337        let policy = policy("api.capacity-rollback", 1, Duration::from_millis(100), 2);
1338        let earlier = Check::new(&policy, subject(1));
1339        let occupying = Check::new(&policy, subject(2));
1340        let new_key = Check::new(&policy, subject(3));
1341        assert!(store.check(&earlier).unwrap().is_allowed());
1342        assert!(store.check(&occupying).unwrap().is_allowed());
1343
1344        assert!(matches!(
1345            store.check_all(&[earlier, new_key]).unwrap(),
1346            BatchDecision::Denied {
1347                index: 1,
1348                denial: Denial::StorageCapacity { .. },
1349            }
1350        ));
1351        assert!(
1352            store.check(&earlier).unwrap().is_allowed(),
1353            "a capacity-denied batch must not consume an earlier member"
1354        );
1355    }
1356
1357    #[test]
1358    fn atomic_batches_preserve_order_and_roll_back_on_shadow_denial() {
1359        let store =
1360            GcraStore::with_clock(MemoryStoreConfig::new(8).unwrap(), ManualClock::default());
1361        let shadow =
1362            policy("api.read", 1, Duration::from_secs(1), 1).with_quota_mode(QuotaMode::Shadow);
1363        let first = Check::new(&shadow, subject(1));
1364        let second = Check::new(&shadow, subject(2));
1365
1366        assert!(store.check(&first).unwrap().is_allowed());
1367        assert!(matches!(
1368            store.check_all(&[first, second]).unwrap(),
1369            BatchDecision::ShadowDenied { index: 0, .. }
1370        ));
1371        assert!(
1372            store.check(&second).unwrap().is_allowed(),
1373            "a shadow-denied batch must not consume any member"
1374        );
1375    }
1376
1377    #[test]
1378    fn storage_capacity_is_enforced_for_shadow_policies() {
1379        let store =
1380            GcraStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default());
1381        let shadow =
1382            policy("api.read", 1, Duration::from_secs(1), 1).with_quota_mode(QuotaMode::Shadow);
1383
1384        assert!(
1385            store
1386                .check(&Check::new(&shadow, subject(1)))
1387                .unwrap()
1388                .is_allowed()
1389        );
1390        let decision = store.check(&Check::new(&shadow, subject(2))).unwrap();
1391        assert!(decision.is_enforced_denial());
1392        assert!(matches!(
1393            decision.denial(),
1394            Some(Denial::StorageCapacity { .. })
1395        ));
1396    }
1397
1398    #[test]
1399    fn extreme_clock_values_fail_closed_without_mutation() {
1400        let store = GcraStore::with_clock(MemoryStoreConfig::new(1).unwrap(), MaximumClock);
1401        let policy = policy("api.read", MAX_LIMIT, Duration::from_millis(1), 1);
1402        let check = Check::new(&policy, subject(1));
1403
1404        assert_eq!(
1405            store.check(&check),
1406            Err(MemoryStoreError::ArithmeticOverflow)
1407        );
1408        assert_eq!(store.stats().unwrap().entries(), 0);
1409    }
1410
1411    #[test]
1412    fn arithmetic_preflight_preserves_expired_entries_and_emits_only_failure() {
1413        let clock = SwitchableExtremeClock::default();
1414        let observer = Arc::new(RecordingObserver::default());
1415        let store = GcraStore::with_clock(MemoryStoreConfig::new(1).unwrap(), clock.clone())
1416            .with_observer(observer.clone());
1417        let ordinary = policy("api.ordinary", 1, Duration::from_millis(1), 1);
1418        assert!(
1419            store
1420                .check(&Check::new(&ordinary, subject(1)))
1421                .unwrap()
1422                .is_allowed()
1423        );
1424        observer.take();
1425
1426        clock.use_extreme_time();
1427        let overflowing = policy("api.overflowing", MAX_LIMIT, Duration::from_millis(1), 1);
1428        assert_eq!(
1429            store.check(&Check::new(&overflowing, subject(2))),
1430            Err(MemoryStoreError::ArithmeticOverflow)
1431        );
1432        assert_eq!(
1433            store.stats().unwrap().entries(),
1434            1,
1435            "arithmetic preflight must fail before pruning the now-expired entry"
1436        );
1437        assert_eq!(
1438            observer.take(),
1439            vec![RecordedObservation::Admission {
1440                outcome: AdmissionOutcome::Failed,
1441                consumption: ConsumptionStatus::NotConsumed,
1442            }]
1443        );
1444    }
1445
1446    #[test]
1447    fn generic_limiter_contract_selects_gcra_policy() {
1448        fn accepts_gcra_limiter<L: runlimit_core::Limiter<Policy = GcraPolicy>>(_limiter: &L) {}
1449
1450        let store =
1451            GcraStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default());
1452        accepts_gcra_limiter(&store);
1453    }
1454}