Skip to main content

runlimit_memory/
gcra.rs

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