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#[derive(Clone, Debug, Error, Eq, PartialEq)]
97#[non_exhaustive]
98pub enum GcraStoreError {
99 #[error(transparent)]
101 Store(#[from] MemoryStoreError),
102 #[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
154pub 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 pub fn new(config: MemoryStoreConfig) -> Self {
182 Self::with_clock(config, SystemClock::new())
183 }
184}
185
186impl<C: Clock> GcraStore<C> {
187 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 #[must_use]
200 pub fn with_observer(mut self, observer: Arc<dyn Observer>) -> Self {
201 self.observer = Some(observer);
202 self
203 }
204
205 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 #[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 pub fn stats(&self) -> Result<MemoryStoreStats, MemoryStoreError> {
436 self.shards.stats(&self.config)
437 }
438
439 pub fn clear(&self) -> Result<(), MemoryStoreError> {
445 self.shards.clear()
446 }
447
448 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}