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
260pub 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 pub fn new(config: MemoryStoreConfig) -> Self {
292 Self::with_clock(config, SystemClock::new())
293 }
294}
295
296impl<C: Clock> GcraStore<C> {
297 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 #[must_use]
313 pub fn with_observer(mut self, observer: Arc<dyn Observer>) -> Self {
314 self.observer = Some(observer);
315 self
316 }
317
318 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 #[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 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 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 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}