1use std::{
2 fmt,
3 sync::Arc,
4 time::{Duration, Instant},
5};
6
7use runlimit_core::{
8 AdmissionObservation, BatchDecision, BatchError, CapacityObservation, Check,
9 CleanupObservation, ConsumptionStatus, CounterKey, Decision, Denial, Limiter, Observation,
10 Observer, QuotaDenial, observe_safely, validate_batch,
11};
12use thiserror::Error;
13
14use crate::{
15 Clock, MemoryStoreConfig, 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 used: u64,
25}
26
27impl Shard<Entry> {
28 fn quota_denial(&self, check: &PreparedCheck, now_millis: u128) -> Option<QuotaDenial> {
29 let (entry, expires_at_millis) = self.active_entry(check.counter_key, now_millis)?;
30 let remaining = remaining_quota(check.limit, entry.used);
31 (check.cost > remaining).then(|| {
32 QuotaDenial::try_new(
33 check.limit,
34 duration_from_millis(expires_at_millis.saturating_sub(now_millis)),
35 )
36 .expect("prepared policy limits are validated")
37 })
38 }
39
40 fn consume(&mut self, check: &PreparedCheck, now_millis: u128) -> Decision {
41 let expires_at_millis = now_millis + u128::from(check.window_millis);
42 if let Some((entry, active_expires_at_millis)) =
43 self.active_entry(check.counter_key, now_millis)
44 {
45 let remaining = remaining_quota(check.limit, entry.used);
46 debug_assert!(
47 check.cost <= remaining,
48 "quota denial must be checked before consumption"
49 );
50 self.update_value(check.counter_key, |entry| {
51 entry.used = entry.used.saturating_add(check.cost);
52 })
53 .expect("the active entry was present");
54 return Decision::allowed(
55 check.limit,
56 remaining.saturating_sub(check.cost),
57 duration_from_millis(active_expires_at_millis.saturating_sub(now_millis)),
58 );
59 }
60
61 self.replace(
62 check.counter_key,
63 Entry { used: check.cost },
64 expires_at_millis,
65 );
66 Decision::allowed(
67 check.limit,
68 remaining_quota(check.limit, check.cost),
69 duration_from_millis(expires_at_millis.saturating_sub(now_millis)),
70 )
71 }
72}
73
74#[derive(Debug)]
75struct PreparedCheck {
76 input_index: usize,
77 counter_key: CounterKey,
78 shard_position: usize,
79 limit: u64,
80 window_millis: u64,
81 cost: u64,
82}
83
84impl PreparedCheck {
85 fn new(input_index: usize, check: &Check<'_>, shard_position: usize) -> Self {
86 Self {
87 input_index,
88 counter_key: check.counter_key(),
89 shard_position,
90 limit: check.policy().limit(),
91 window_millis: check.policy().window_millis(),
92 cost: check.cost(),
93 }
94 }
95}
96
97#[derive(Debug)]
98struct Evaluation<T, E> {
99 value: T,
100 effect: E,
101}
102
103pub struct MemoryStore<C = SystemClock> {
115 config: MemoryStoreConfig,
116 clock: C,
117 shards: BoundedShards<Entry>,
118 observer: Option<Arc<dyn Observer>>,
119}
120
121impl<C> fmt::Debug for MemoryStore<C> {
122 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
123 let poisoned_shards = self.shards.poisoned_count();
124
125 formatter
126 .debug_struct("MemoryStore")
127 .field("config", &self.config)
128 .field("has_observer", &self.observer.is_some())
129 .field("poisoned_shards", &poisoned_shards)
130 .field("shard_state", &Redacted)
131 .finish_non_exhaustive()
132 }
133}
134
135struct Redacted;
136
137impl fmt::Debug for Redacted {
138 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
139 formatter.write_str("[REDACTED]")
140 }
141}
142
143impl MemoryStore<SystemClock> {
144 pub fn new(config: MemoryStoreConfig) -> Self {
146 Self::with_clock(config, SystemClock::new())
147 }
148}
149
150impl<C: Clock> MemoryStore<C> {
151 pub fn with_clock(config: MemoryStoreConfig, clock: C) -> Self {
155 let shards = BoundedShards::new(&config);
156
157 Self {
158 config,
159 clock,
160 shards,
161 observer: None,
162 }
163 }
164
165 #[must_use]
170 pub fn with_observer(mut self, observer: Arc<dyn Observer>) -> Self {
171 self.observer = Some(observer);
172 self
173 }
174
175 fn observe_shard_effects(&self, effects: &[ShardEffect]) {
176 for effect in effects {
177 self.observe_shard_effect(effect);
178 }
179 }
180
181 fn observe_shard_effect(&self, effect: &ShardEffect) {
182 let Some(observer) = &self.observer else {
183 return;
184 };
185
186 observe_safely(
187 observer.as_ref(),
188 &Observation::Cleanup(CleanupObservation::confirmed(
189 effect.cleanup.requested,
190 usize_to_u64(effect.cleanup.removed),
191 effect.cleanup.elapsed,
192 )),
193 );
194 observe_safely(
195 observer.as_ref(),
196 &Observation::Capacity(CapacityObservation::new(
197 usize_to_u64(effect.used),
198 usize_to_u64(effect.capacity),
199 Some(effect.shard_index),
200 )),
201 );
202 }
203
204 fn observe_admission<'a>(&self, build_observation: impl FnOnce() -> AdmissionObservation<'a>) {
205 let Some(observer) = &self.observer else {
206 return;
207 };
208 let admission = build_observation();
209 observe_safely(observer.as_ref(), &Observation::Admission(admission));
210 }
211
212 pub fn check(&self, check: &Check<'_>) -> Result<Decision, MemoryStoreError> {
219 let started = Instant::now();
220 let result = self.check_inner(check);
221 let elapsed = started.elapsed();
222
223 match &result {
224 Ok(evaluation) => {
225 self.observe_shard_effect(&evaluation.effect);
226 self.observe_admission(|| {
227 AdmissionObservation::from_check(check, &evaluation.value, elapsed)
228 });
229 }
230 Err(_) => self.observe_admission(|| {
231 AdmissionObservation::failed_check(check, ConsumptionStatus::NotConsumed, elapsed)
232 }),
233 }
234
235 result.map(|evaluation| evaluation.value)
236 }
237
238 fn check_inner(
239 &self,
240 check: &Check<'_>,
241 ) -> Result<Evaluation<Decision, ShardEffect>, MemoryStoreError> {
242 let counter_key = check.counter_key();
243 let shard_index = self.shards.shard_index(&counter_key);
244 let prepared = PreparedCheck::new(0, check, 0);
245 let mut shard = self.shards.lock_shard(shard_index)?;
246 let observed_millis = self.clock.now().as_millis();
247 let now_millis = observed_millis.max(shard.latest_observed_millis());
248 shard.record_observed_millis(now_millis);
249 let cleanup_requested = self.config.max_expired_removals_per_check();
250 let cleanup_started = Instant::now();
251 let cleanup_removed = shard.prune_expired(now_millis, cleanup_requested);
252 let cleanup_elapsed = cleanup_started.elapsed();
253
254 let decision = if let Some(denial) = shard.quota_denial(&prepared, now_millis) {
255 if check.policy().quota_mode() == runlimit_core::QuotaMode::Shadow {
256 Decision::shadow_denied(denial)
257 } else {
258 Decision::denied(denial)
259 }
260 } else if !shard.contains_key(counter_key) && shard.used() >= shard.capacity() {
261 Decision::denied(Denial::storage_capacity(
262 shard
263 .capacity_retry_after_millis(now_millis)
264 .map(duration_from_millis),
265 ))
266 } else {
267 shard.consume(&prepared, now_millis)
268 };
269
270 Ok(Evaluation {
271 value: decision,
272 effect: ShardEffect {
273 shard_index,
274 cleanup: CleanupEffect {
275 requested: cleanup_requested,
276 removed: cleanup_removed,
277 elapsed: cleanup_elapsed,
278 },
279 used: shard.used(),
280 capacity: shard.capacity(),
281 },
282 })
283 }
284
285 #[allow(clippy::too_many_lines)]
298 pub fn check_all(&self, checks: &[Check<'_>]) -> Result<BatchDecision, MemoryStoreError> {
299 let started = Instant::now();
300 let result = self.check_all_inner(checks);
301 let elapsed = started.elapsed();
302
303 match &result {
304 Ok(evaluation) => {
305 self.observe_shard_effects(&evaluation.effect);
306 self.observe_admission(|| {
307 AdmissionObservation::from_batch(checks, &evaluation.value, elapsed)
308 });
309 }
310 Err(_) => self.observe_admission(|| {
311 AdmissionObservation::failed_batch(
312 checks.len(),
313 ConsumptionStatus::NotConsumed,
314 elapsed,
315 )
316 }),
317 }
318
319 result.map(|evaluation| evaluation.value)
320 }
321
322 #[allow(clippy::too_many_lines)]
323 fn check_all_inner(
324 &self,
325 checks: &[Check<'_>],
326 ) -> Result<Evaluation<BatchDecision, Vec<ShardEffect>>, MemoryStoreError> {
327 validate_batch(checks, self.config.max_batch_size())?;
328 if checks.is_empty() {
329 return Ok(Evaluation {
330 value: BatchDecision::allowed(Vec::new()),
331 effect: Vec::new(),
332 });
333 }
334
335 let topology = BatchTopology::new(
336 checks
337 .iter()
338 .map(|check| self.shards.shard_index(&check.counter_key())),
339 &self.config,
340 )?;
341 let prepared = checks
342 .iter()
343 .enumerate()
344 .map(|(input_index, check)| {
345 PreparedCheck::new(input_index, check, topology.shard_position(input_index))
346 })
347 .collect::<Vec<_>>();
348
349 let mut locked_shards = self.shards.lock_topology(&topology)?;
350 let observed_millis = self.clock.now().as_millis();
351 let now_millis = locked_shards
352 .iter()
353 .map(|(_, shard)| shard.latest_observed_millis())
354 .fold(observed_millis, u128::max);
355 let mut cleanup_effects = Vec::with_capacity(locked_shards.len());
356 for ((_, shard), check_count) in locked_shards.iter_mut().zip(topology.check_counts()) {
357 shard.record_observed_millis(now_millis);
358 let cleanup_limit = self
359 .config
360 .max_expired_removals_per_check()
361 .saturating_mul(check_count);
362 let cleanup_started = Instant::now();
363 let removed = shard.prune_expired(now_millis, cleanup_limit);
364 cleanup_effects.push(CleanupEffect {
365 requested: cleanup_limit,
366 removed,
367 elapsed: cleanup_started.elapsed(),
368 });
369 }
370
371 let mut pending_insertions = vec![0_usize; locked_shards.len()];
372 for check in &prepared {
373 let shard = &locked_shards[check.shard_position].1;
374 if let Some(denial) = shard.quota_denial(check, now_millis) {
375 let value = if checks[check.input_index].policy().quota_mode()
376 == runlimit_core::QuotaMode::Shadow
377 {
378 BatchDecision::shadow_denied(check.input_index, denial)
379 } else {
380 BatchDecision::denied(check.input_index, denial)
381 };
382 return Ok(Evaluation {
383 value,
384 effect: collect_shard_effects(&locked_shards, &cleanup_effects),
385 });
386 }
387
388 if !shard.contains_key(check.counter_key) {
389 let projected_len = shard.used() + pending_insertions[check.shard_position];
390 if projected_len >= shard.capacity() {
391 return Ok(Evaluation {
392 value: BatchDecision::denied(
393 check.input_index,
394 Denial::storage_capacity(
395 shard
396 .capacity_retry_after_millis(now_millis)
397 .map(duration_from_millis),
398 ),
399 ),
400 effect: collect_shard_effects(&locked_shards, &cleanup_effects),
401 });
402 }
403 pending_insertions[check.shard_position] += 1;
404 }
405 }
406
407 let mut decisions = Vec::with_capacity(prepared.len());
408 for check in &prepared {
409 let shard = &mut locked_shards[check.shard_position].1;
410 decisions.push(shard.consume(check, now_millis));
411 }
412
413 Ok(Evaluation {
414 value: BatchDecision::allowed(decisions),
415 effect: collect_shard_effects(&locked_shards, &cleanup_effects),
416 })
417 }
418
419 pub fn stats(&self) -> Result<MemoryStoreStats, MemoryStoreError> {
425 self.shards.stats(&self.config)
426 }
427
428 pub fn clear(&self) -> Result<(), MemoryStoreError> {
434 self.shards.clear()
435 }
436
437 pub fn recover_poisoned(&self) -> usize {
451 self.shards.recover_poisoned(&self.config)
452 }
453}
454
455fn remaining_quota(limit: u64, used: u64) -> u64 {
456 debug_assert!(
457 used <= limit,
458 "stored quota usage ({used}) exceeded its policy limit ({limit})"
459 );
460 limit.saturating_sub(used)
461}
462
463impl<C: Clock> Limiter for MemoryStore<C> {
464 type Policy = runlimit_core::FixedWindowPolicy;
465 type Error = MemoryStoreError;
466
467 fn check(
468 &self,
469 check: &Check<'_>,
470 ) -> impl Future<Output = Result<Decision, Self::Error>> + Send {
471 std::future::ready(MemoryStore::check(self, check))
472 }
473
474 fn check_all(
475 &self,
476 checks: &[Check<'_>],
477 ) -> impl Future<Output = Result<BatchDecision, Self::Error>> + Send {
478 std::future::ready(MemoryStore::check_all(self, checks))
479 }
480}
481
482fn duration_from_millis(millis: u128) -> Duration {
483 Duration::from_millis(
484 u64::try_from(millis)
485 .expect("a counter's remaining duration cannot exceed its portable policy window"),
486 )
487}
488
489#[derive(Clone, Copy, Debug, Eq, PartialEq)]
494pub struct MemoryStoreStats {
495 entries: usize,
496 capacity: usize,
497 shard_count: usize,
498}
499
500impl MemoryStoreStats {
501 pub(crate) const fn from_parts(entries: usize, capacity: usize, shard_count: usize) -> Self {
502 Self {
503 entries,
504 capacity,
505 shard_count,
506 }
507 }
508
509 pub const fn entries(self) -> usize {
511 self.entries
512 }
513
514 pub const fn capacity(self) -> usize {
516 self.capacity
517 }
518
519 pub const fn shard_count(self) -> usize {
521 self.shard_count
522 }
523}
524
525#[cfg(feature = "serde")]
526#[derive(serde::Serialize)]
527struct MemoryStoreStatsWire {
528 entries: usize,
529 capacity: usize,
530 shard_count: usize,
531}
532
533#[cfg(feature = "serde")]
534impl serde::Serialize for MemoryStoreStats {
535 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
536 where
537 S: serde::Serializer,
538 {
539 serde::Serialize::serialize(
540 &MemoryStoreStatsWire {
541 entries: self.entries(),
542 capacity: self.capacity(),
543 shard_count: self.shard_count(),
544 },
545 serializer,
546 )
547 }
548}
549
550#[derive(Clone, Debug, Error, Eq, PartialEq)]
552pub enum MemoryStoreError {
553 #[error(transparent)]
555 InvalidBatch(#[from] BatchError),
556 #[error(
558 "batch targets {key_count} distinct keys at memory-store shard {shard_index}, \
559 but that shard can store at most {capacity}"
560 )]
561 BatchExceedsShardCapacity {
562 shard_index: usize,
564 key_count: usize,
566 capacity: usize,
568 },
569 #[error("memory-store shard {shard_index} is poisoned and unavailable")]
571 PoisonedShard {
572 shard_index: usize,
574 },
575}
576
577#[cfg(test)]
578mod tests {
579 use std::{
580 sync::{
581 Arc, Barrier, Mutex, Weak,
582 atomic::{AtomicBool, AtomicU64, AtomicUsize, Ordering},
583 mpsc,
584 },
585 thread,
586 time::Duration,
587 };
588
589 use runlimit_core::{
590 AdmissionOperation, AdmissionOutcome, BatchDecision, BatchError, Check, ConsumptionStatus,
591 Decision, Denial, DenialKind, FixedWindowPolicy, KeyHasher, MAX_LIMIT, MAX_WINDOW,
592 MAX_WINDOW_MILLIS, Observation, Observer, PolicyId, QuotaDenial, QuotaMode, ScopeId,
593 SubjectKey,
594 };
595
596 use super::{Entry, MemoryStore, MemoryStoreError, remaining_quota};
597 use crate::{Clock, MemoryStoreConfig, shards::counter_key_hash};
598
599 fn quota(capacity: u64, retry_after: Duration) -> QuotaDenial {
600 QuotaDenial::try_new(capacity, retry_after).unwrap()
601 }
602
603 #[derive(Clone, Default)]
604 struct ManualClock {
605 now_millis: Arc<AtomicU64>,
606 }
607
608 impl ManualClock {
609 fn advance(&self, duration: Duration) {
610 let millis = u64::try_from(duration.as_millis()).unwrap();
611 self.now_millis.fetch_add(millis, Ordering::Relaxed);
612 }
613
614 fn set(&self, duration: Duration) {
615 let millis = u64::try_from(duration.as_millis()).unwrap();
616 self.now_millis.store(millis, Ordering::Relaxed);
617 }
618 }
619
620 impl Clock for ManualClock {
621 fn now(&self) -> Duration {
622 Duration::from_millis(self.now_millis.load(Ordering::Relaxed))
623 }
624 }
625
626 #[derive(Clone, Default)]
627 struct PanicOnceClock {
628 panic_next: Arc<AtomicBool>,
629 }
630
631 impl PanicOnceClock {
632 fn panic_once(&self) {
633 self.panic_next.store(true, Ordering::Relaxed);
634 }
635 }
636
637 impl Clock for PanicOnceClock {
638 fn now(&self) -> Duration {
639 assert!(
640 !self.panic_next.swap(false, Ordering::Relaxed),
641 "panic from test clock"
642 );
643 Duration::ZERO
644 }
645 }
646
647 #[derive(Clone)]
648 struct WideManualClock {
649 now_millis: Arc<Mutex<u128>>,
650 }
651
652 impl WideManualClock {
653 fn new(now_millis: u128) -> Self {
654 Self {
655 now_millis: Arc::new(Mutex::new(now_millis)),
656 }
657 }
658
659 fn advance(&self, millis: u128) {
660 let mut now_millis = self.now_millis.lock().unwrap();
661 *now_millis += millis;
662 }
663 }
664
665 impl Clock for WideManualClock {
666 fn now(&self) -> Duration {
667 let millis = *self.now_millis.lock().unwrap();
668 let seconds = u64::try_from(millis / 1_000).unwrap();
669 let subsec_millis = u32::try_from(millis % 1_000).unwrap();
670 Duration::new(seconds, subsec_millis * 1_000_000)
671 }
672 }
673
674 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
675 enum RecordedObservation {
676 Admission(AdmissionOutcome, ConsumptionStatus, usize),
677 Cleanup(usize, Option<u64>),
678 Capacity(u64, u64, u64),
679 }
680
681 #[derive(Default)]
682 struct RecordingObserver {
683 observations: Mutex<Vec<RecordedObservation>>,
684 }
685
686 impl Observer for RecordingObserver {
687 fn observe(&self, observation: &Observation<'_>) {
688 let owned = match observation {
689 Observation::Admission(admission) => RecordedObservation::Admission(
690 admission.outcome(),
691 admission.consumption(),
692 admission.batch_size(),
693 ),
694 Observation::Cleanup(cleanup) => {
695 RecordedObservation::Cleanup(cleanup.requested(), cleanup.removed())
696 }
697 Observation::Capacity(capacity) => RecordedObservation::Capacity(
698 capacity.used(),
699 capacity.capacity(),
700 capacity.headroom(),
701 ),
702 _ => return,
703 };
704 self.observations.lock().unwrap().push(owned);
705 }
706 }
707
708 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
709 struct RecordedAdmissionMetadata {
710 operation: AdmissionOperation,
711 batch_size: usize,
712 has_policy_id: bool,
713 has_scope_id: bool,
714 has_policy_fingerprint: bool,
715 outcome: AdmissionOutcome,
716 consumption: ConsumptionStatus,
717 }
718
719 #[derive(Default)]
720 struct AdmissionMetadataObserver {
721 admissions: Mutex<Vec<RecordedAdmissionMetadata>>,
722 }
723
724 impl Observer for AdmissionMetadataObserver {
725 fn observe(&self, observation: &Observation<'_>) {
726 let Observation::Admission(admission) = observation else {
727 return;
728 };
729 self.admissions
730 .lock()
731 .unwrap()
732 .push(RecordedAdmissionMetadata {
733 operation: admission.operation(),
734 batch_size: admission.batch_size(),
735 has_policy_id: admission.policy_id().is_some(),
736 has_scope_id: admission.scope_id().is_some(),
737 has_policy_fingerprint: admission.policy_fingerprint().is_some(),
738 outcome: admission.outcome(),
739 consumption: admission.consumption(),
740 });
741 }
742 }
743
744 struct ReentrantObserver {
745 store: Mutex<Option<Weak<MemoryStore<ManualClock>>>>,
746 calls: AtomicUsize,
747 }
748
749 impl Observer for ReentrantObserver {
750 fn observe(&self, _observation: &Observation<'_>) {
751 self.calls.fetch_add(1, Ordering::Relaxed);
752 if let Some(store) = self.store.lock().unwrap().as_ref().and_then(Weak::upgrade) {
753 store.stats().unwrap();
754 }
755 }
756 }
757
758 struct PanickingObserver;
759
760 impl Observer for PanickingObserver {
761 fn observe(&self, _observation: &Observation<'_>) {
762 panic!("observer failure");
763 }
764 }
765
766 fn policy(policy_id: &str, scope_id: &str, limit: u64, window: Duration) -> FixedWindowPolicy {
767 FixedWindowPolicy::new(
768 PolicyId::new(policy_id).unwrap(),
769 ScopeId::new(scope_id).unwrap(),
770 limit,
771 window,
772 )
773 .unwrap()
774 }
775
776 fn subject(byte: u8) -> SubjectKey {
777 SubjectKey::from_digest([byte; 32])
778 }
779
780 fn subjects_for_shard<C: Clock>(
781 store: &MemoryStore<C>,
782 policy: &FixedWindowPolicy,
783 shard_index: usize,
784 count: usize,
785 ) -> Vec<SubjectKey> {
786 assert!(shard_index < store.shards.len());
787 let mut subjects = Vec::with_capacity(count);
788
789 for value in 0_u64..10_000 {
790 let mut digest = [0_u8; 32];
791 digest[..8].copy_from_slice(&value.to_le_bytes());
792 let candidate = SubjectKey::from_digest(digest);
793 let counter_key = Check::new(policy, candidate).counter_key();
794 if store.shards.shard_index(&counter_key) == shard_index {
795 subjects.push(candidate);
796 if subjects.len() == count {
797 break;
798 }
799 }
800 }
801
802 assert_eq!(
803 subjects.len(),
804 count,
805 "could not find enough subjects for shard {shard_index}"
806 );
807 subjects
808 }
809
810 #[test]
811 fn hmac_subjects_are_evenly_and_deterministically_sharded() {
812 const SHARD_COUNT: usize = 16;
813 const SUBJECT_COUNT: u64 = 4_096;
814
815 let config = MemoryStoreConfig::new(SHARD_COUNT)
816 .unwrap()
817 .with_shard_count(SHARD_COUNT)
818 .unwrap();
819 let first = MemoryStore::with_clock(config.clone(), ManualClock::default());
820 let second = MemoryStore::with_clock(config, ManualClock::default());
821 let policy = policy("auth.login", "client", 2, Duration::from_secs(60));
822 let key_hasher = KeyHasher::new([0x42; 32]).unwrap();
823 let mut counts = [0_usize; SHARD_COUNT];
824
825 for value in 0_u64..SUBJECT_COUNT {
826 let subject = key_hasher.hash_for(&policy, value.to_le_bytes());
827 let key = Check::new(&policy, subject).counter_key();
828 let first_index = first.shards.shard_index(&key);
829
830 assert_eq!(first_index, second.shards.shard_index(&key));
831 counts[first_index] += 1;
832 }
833
834 assert!(
835 counts.iter().all(|&count| (176..=336).contains(&count)),
836 "uniform HMAC output should spread across every shard: {counts:?}"
837 );
838 }
839
840 #[test]
841 fn the_entries_map_distinguishes_deliberate_prehash_collisions() {
842 let first_policy = policy("auth.login", "client", 1, Duration::from_secs(60));
843 let second_policy = policy("auth.reset", "client", 2, Duration::from_secs(60));
844 let first_subject = SubjectKey::from_digest([0_u8; 32]);
845 let first_key = Check::new(&first_policy, first_subject).counter_key();
846
847 let zero_second_key =
848 Check::new(&second_policy, SubjectKey::from_digest([0_u8; 32])).counter_key();
849 let colliding_subject_word =
850 counter_key_hash(first_key) ^ counter_key_hash(zero_second_key);
851 let mut second_digest = [0_u8; 32];
852 second_digest[..8].copy_from_slice(&colliding_subject_word.to_le_bytes());
853 let second_subject = SubjectKey::from_digest(second_digest);
854 let second_key = Check::new(&second_policy, second_subject).counter_key();
855
856 assert_ne!(first_key, second_key);
857 assert_eq!(counter_key_hash(first_key), counter_key_hash(second_key));
858
859 let store =
860 MemoryStore::with_clock(MemoryStoreConfig::new(4).unwrap(), ManualClock::default());
861 let first_check = Check::new(&first_policy, first_subject);
862 let second_check = Check::new(&second_policy, second_subject);
863
864 assert!(store.check(&first_check).unwrap().is_allowed());
865 assert!(store.check(&second_check).unwrap().is_allowed());
866 assert_eq!(store.stats().unwrap().entries(), 2);
867 assert!(store.check(&first_check).unwrap().is_denied());
868 assert!(store.check(&second_check).unwrap().is_allowed());
869 }
870
871 #[test]
872 fn remaining_quota_reaches_zero_without_wrapping() {
873 assert_eq!(remaining_quota(3, 0), 3);
874 assert_eq!(remaining_quota(3, 3), 0);
875 }
876
877 #[cfg(debug_assertions)]
878 #[test]
879 #[should_panic(expected = "stored quota usage (4) exceeded its policy limit (3)")]
880 fn corrupt_quota_state_trips_the_debug_invariant() {
881 let _ = remaining_quota(3, 4);
882 }
883
884 #[cfg(not(debug_assertions))]
885 #[test]
886 fn corrupt_quota_state_fails_closed_in_release_builds() {
887 let policy = policy("auth.login", "client", 3, Duration::from_secs(60));
888 let check = Check::new(&policy, subject(1));
889 let key = check.counter_key();
890 let store =
891 MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default());
892 {
893 let mut shard = store.shards.shard(0).lock().unwrap();
894 assert!(shard.replace(key, Entry { used: 4 }, 60_000).is_none());
895 }
896
897 assert_eq!(
898 store.check(&check),
899 Ok(Decision::denied(quota(3, Duration::from_secs(60))))
900 );
901 }
902
903 #[test]
904 fn debug_output_is_useful_without_exposing_counter_state() {
905 let store =
906 MemoryStore::with_clock(MemoryStoreConfig::new(8).unwrap(), ManualClock::default());
907 let policy = policy("auth.login", "client", 2, Duration::from_secs(60));
908 store
909 .check(&Check::new(&policy, subject(0xab)))
910 .expect("store is available");
911
912 let output = format!("{store:?}");
913
914 assert!(output.starts_with("MemoryStore { config: MemoryStoreConfig"));
915 assert!(output.contains("max_keys: 8"));
916 assert!(output.contains("poisoned_shards: 0"));
917 assert!(output.contains("shard_state: [REDACTED]"));
918 assert!(!output.contains("CounterKey"));
919 assert!(!output.contains("expires_at_millis"));
920 assert!(!output.contains("used:"));
921 }
922
923 #[test]
924 fn enforces_quota_and_reports_exact_retry_duration() {
925 let clock = ManualClock::default();
926 let store = MemoryStore::with_clock(MemoryStoreConfig::new(8).unwrap(), clock.clone());
927 let policy = policy("auth.login", "client", 2, Duration::from_secs(60));
928 let check = Check::new(&policy, subject(1));
929
930 let first = store.check(&check).unwrap();
931 assert!(first.is_allowed());
932 assert_eq!(first.available(), Some(1));
933 assert_eq!(first.retry_after(), None);
934
935 let second = store.check(&check).unwrap();
936 assert!(second.is_allowed());
937 assert_eq!(second.available(), Some(0));
938
939 let denied = store.check(&check).unwrap();
940 assert!(!denied.is_allowed());
941 assert_eq!(denied.retry_after(), Some(Duration::from_secs(60)));
942
943 clock.advance(Duration::from_secs(10));
944 assert_eq!(
945 store.check(&check).unwrap().retry_after(),
946 Some(Duration::from_secs(50))
947 );
948
949 clock.advance(Duration::from_secs(50));
950 let reset = store.check(&check).unwrap();
951 assert!(reset.is_allowed());
952 assert_eq!(reset.available(), Some(1));
953 assert_eq!(reset.replenishes_after(), Some(Duration::from_secs(60)));
954 }
955
956 #[test]
957 fn shadow_mode_reports_quota_without_consuming_or_rejecting() {
958 let clock = ManualClock::default();
959 let store = MemoryStore::with_clock(MemoryStoreConfig::new(4).unwrap(), clock.clone());
960 let enforced = policy("auth.login", "client", 1, Duration::from_secs(60));
961 let shadow = enforced.clone().with_quota_mode(QuotaMode::Shadow);
962 let subject = subject(7);
963
964 assert!(
965 store
966 .check(&Check::new(&shadow, subject))
967 .unwrap()
968 .is_allowed()
969 );
970 let shadow_denial = store.check(&Check::new(&shadow, subject)).unwrap();
971 assert!(shadow_denial.permits_request());
972 assert!(shadow_denial.is_shadow_denied());
973 assert_eq!(
974 shadow_denial.denial().map(Denial::kind),
975 Some(DenialKind::QuotaExceeded)
976 );
977
978 let enforced_denial = store.check(&Check::new(&enforced, subject)).unwrap();
979 assert!(enforced_denial.is_enforced_denial());
980 assert_eq!(
981 enforced_denial.denial().map(Denial::kind),
982 Some(DenialKind::QuotaExceeded)
983 );
984
985 clock.advance(Duration::from_secs(60));
986 assert!(
987 store
988 .check(&Check::new(&enforced, subject))
989 .unwrap()
990 .is_allowed()
991 );
992 }
993
994 #[test]
995 fn shadow_batches_roll_back_and_capacity_denials_remain_enforced() {
996 let store =
997 MemoryStore::with_clock(MemoryStoreConfig::new(3).unwrap(), ManualClock::default());
998 let shadow = policy("auth.login", "client", 1, Duration::from_secs(60))
999 .with_quota_mode(QuotaMode::Shadow);
1000 let first = Check::new(&shadow, subject(1));
1001 let second = Check::new(&shadow, subject(2));
1002
1003 assert!(store.check(&first).unwrap().is_allowed());
1004 let result = store.check_all(&[first, second]).unwrap();
1005 assert!(result.is_shadow_denied());
1006 assert_eq!(result.denied_index(), Some(0));
1007 assert!(
1008 store.check(&second).unwrap().is_allowed(),
1009 "a shadow-denied atomic batch must not consume another check"
1010 );
1011
1012 let full_store =
1013 MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default());
1014 assert!(full_store.check(&first).unwrap().is_allowed());
1015 let capacity = full_store.check(&second).unwrap();
1016 assert!(capacity.is_enforced_denial());
1017 assert_eq!(
1018 capacity.denial().map(Denial::kind),
1019 Some(DenialKind::StorageCapacity)
1020 );
1021 }
1022
1023 #[test]
1024 fn mixed_shadow_and_enforced_batches_fail_before_consumption() {
1025 let store =
1026 MemoryStore::with_clock(MemoryStoreConfig::new(4).unwrap(), ManualClock::default());
1027 let enforced = policy("auth.login", "client", 1, Duration::from_secs(60));
1028 let shadow = policy("auth.reset", "client", 1, Duration::from_secs(60))
1029 .with_quota_mode(QuotaMode::Shadow);
1030 let result = store.check_all(&[
1031 Check::new(&enforced, subject(1)),
1032 Check::new(&shadow, subject(2)),
1033 ]);
1034
1035 assert!(matches!(
1036 result,
1037 Err(MemoryStoreError::InvalidBatch(
1038 BatchError::MixedQuotaModes { index: 1, .. }
1039 ))
1040 ));
1041 assert_eq!(store.stats().unwrap().entries(), 0);
1042 }
1043
1044 #[test]
1045 fn observer_reports_outcomes_cleanup_and_capacity_headroom() {
1046 let observer = Arc::new(RecordingObserver::default());
1047 let store =
1048 MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default())
1049 .with_observer(observer.clone());
1050 let limited = policy("auth.login", "client", 1, Duration::from_secs(60));
1051
1052 assert!(
1053 store
1054 .check(&Check::new(&limited, subject(1)))
1055 .unwrap()
1056 .is_allowed()
1057 );
1058 assert!(
1059 store
1060 .check(&Check::new(&limited, subject(1)))
1061 .unwrap()
1062 .is_denied()
1063 );
1064 assert!(
1065 store
1066 .check(&Check::new(&limited, subject(2)))
1067 .unwrap()
1068 .is_denied()
1069 );
1070
1071 let observations = observer.observations.lock().unwrap().clone();
1072 assert_eq!(observations.len(), 9);
1073 assert!(observations.contains(&RecordedObservation::Admission(
1074 AdmissionOutcome::Allowed,
1075 ConsumptionStatus::Consumed,
1076 1,
1077 )));
1078 assert!(observations.contains(&RecordedObservation::Admission(
1079 AdmissionOutcome::QuotaDenied,
1080 ConsumptionStatus::NotConsumed,
1081 1,
1082 )));
1083 assert!(observations.contains(&RecordedObservation::Admission(
1084 AdmissionOutcome::CapacityDenied,
1085 ConsumptionStatus::NotConsumed,
1086 1,
1087 )));
1088 assert_eq!(
1089 observations
1090 .iter()
1091 .filter(|event| matches!(event, RecordedObservation::Cleanup(8, Some(0))))
1092 .count(),
1093 3
1094 );
1095 assert_eq!(
1096 observations
1097 .iter()
1098 .filter(|event| matches!(event, RecordedObservation::Capacity(1, 1, 0)))
1099 .count(),
1100 3
1101 );
1102 }
1103
1104 #[test]
1105 fn observers_run_after_unlock_and_panics_are_isolated() {
1106 let observer = Arc::new(ReentrantObserver {
1107 store: Mutex::new(None),
1108 calls: AtomicUsize::new(0),
1109 });
1110 let store = Arc::new(
1111 MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default())
1112 .with_observer(observer.clone()),
1113 );
1114 *observer.store.lock().unwrap() = Some(Arc::downgrade(&store));
1115 let limited = policy("auth.login", "client", 1, Duration::from_secs(60));
1116 let check = Check::new(&limited, subject(1));
1117
1118 assert!(store.check(&check).unwrap().is_allowed());
1119 assert_eq!(observer.calls.load(Ordering::Relaxed), 3);
1120
1121 let panicking_store =
1122 MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), ManualClock::default())
1123 .with_observer(Arc::new(PanickingObserver));
1124 assert!(panicking_store.check(&check).unwrap().is_allowed());
1125 assert!(panicking_store.check(&check).unwrap().is_denied());
1126 }
1127
1128 #[test]
1129 fn single_check_matches_a_one_element_batch_across_state_transitions() {
1130 #[derive(Clone, Copy)]
1131 struct Step {
1132 now: Duration,
1133 subject: u8,
1134 cost: u64,
1135 expected: Decision,
1136 }
1137
1138 let config = MemoryStoreConfig::new(2)
1139 .unwrap()
1140 .with_shard_count(1)
1141 .unwrap()
1142 .with_max_expired_removals_per_check(1)
1143 .unwrap();
1144 let single_clock = ManualClock::default();
1145 let batch_clock = ManualClock::default();
1146 let single_store = MemoryStore::with_clock(config.clone(), single_clock.clone());
1147 let batch_store = MemoryStore::with_clock(config, batch_clock.clone());
1148 let policy = policy("auth.login", "client", 5, Duration::from_millis(10));
1149 let steps = [
1150 Step {
1151 now: Duration::ZERO,
1152 subject: 1,
1153 cost: 2,
1154 expected: Decision::allowed(5, 3, Duration::from_millis(10)),
1155 },
1156 Step {
1157 now: Duration::from_millis(3),
1158 subject: 1,
1159 cost: 2,
1160 expected: Decision::allowed(5, 1, Duration::from_millis(7)),
1161 },
1162 Step {
1163 now: Duration::from_millis(3),
1164 subject: 1,
1165 cost: 2,
1166 expected: Decision::denied(quota(5, Duration::from_millis(7))),
1167 },
1168 Step {
1169 now: Duration::from_millis(9),
1170 subject: 1,
1171 cost: 1,
1172 expected: Decision::allowed(5, 0, Duration::from_millis(1)),
1173 },
1174 Step {
1175 now: Duration::from_millis(10),
1176 subject: 1,
1177 cost: 3,
1178 expected: Decision::allowed(5, 2, Duration::from_millis(10)),
1179 },
1180 Step {
1181 now: Duration::from_millis(8),
1182 subject: 1,
1183 cost: 1,
1184 expected: Decision::allowed(5, 1, Duration::from_millis(10)),
1185 },
1186 Step {
1187 now: Duration::from_millis(10),
1188 subject: 2,
1189 cost: 1,
1190 expected: Decision::allowed(5, 4, Duration::from_millis(10)),
1191 },
1192 Step {
1193 now: Duration::from_millis(10),
1194 subject: 3,
1195 cost: 1,
1196 expected: Decision::denied(Denial::storage_capacity(Some(Duration::from_millis(
1197 10,
1198 )))),
1199 },
1200 Step {
1201 now: Duration::from_millis(20),
1202 subject: 3,
1203 cost: 1,
1204 expected: Decision::allowed(5, 4, Duration::from_millis(10)),
1205 },
1206 ];
1207
1208 for (index, step) in steps.into_iter().enumerate() {
1209 single_clock.set(step.now);
1210 batch_clock.set(step.now);
1211 let check = Check::with_cost(&policy, subject(step.subject), step.cost).unwrap();
1212
1213 let single = single_store.check(&check).unwrap();
1214 let batch = batch_store
1215 .check_all(std::slice::from_ref(&check))
1216 .unwrap()
1217 .try_into_single_decision()
1218 .expect("a one-element batch returns one decision");
1219
1220 assert_eq!(single, batch, "step {index}");
1221 assert_eq!(single, step.expected, "step {index}");
1222 }
1223
1224 assert_eq!(single_store.stats().unwrap(), batch_store.stats().unwrap());
1225 }
1226
1227 #[test]
1228 fn windows_remain_exact_across_the_u64_millisecond_boundary() {
1229 let clock = WideManualClock::new(u128::from(u64::MAX));
1230 let store = MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), clock.clone());
1231 let policy = policy("auth.login", "client", MAX_LIMIT, MAX_WINDOW);
1232 let check = Check::with_cost(&policy, subject(1), MAX_LIMIT).unwrap();
1233
1234 let first = store.check(&check).unwrap();
1235 assert!(first.is_allowed());
1236 assert_eq!(first.available(), Some(0));
1237 assert_eq!(first.replenishes_after(), Some(MAX_WINDOW));
1238
1239 let denied = store.check(&check).unwrap();
1240 assert!(denied.is_denied());
1241 assert_eq!(denied.retry_after(), Some(MAX_WINDOW));
1242
1243 clock.advance(u128::from(MAX_WINDOW_MILLIS - 1));
1244 let nearly_reset = store.check(&check).unwrap();
1245 assert!(nearly_reset.is_denied());
1246 assert_eq!(nearly_reset.retry_after(), Some(Duration::from_millis(1)));
1247
1248 clock.advance(1);
1249 let reset = store.check(&check).unwrap();
1250 assert!(reset.is_allowed());
1251 assert_eq!(reset.replenishes_after(), Some(MAX_WINDOW));
1252 }
1253
1254 #[test]
1255 fn policy_configuration_changes_use_independent_counters() {
1256 let store = MemoryStore::with_clock(
1257 MemoryStoreConfig::new(2)
1258 .unwrap()
1259 .with_shard_count(1)
1260 .unwrap(),
1261 ManualClock::default(),
1262 );
1263 let strict = policy("auth.login", "client", 1, Duration::from_secs(60));
1264 let relaxed = policy("auth.login", "client", 2, Duration::from_secs(60));
1265 let key = subject(1);
1266
1267 assert!(store.check(&Check::new(&strict, key)).unwrap().is_allowed());
1268 assert!(
1269 store
1270 .check(&Check::new(&relaxed, key))
1271 .unwrap()
1272 .is_allowed()
1273 );
1274 assert_eq!(store.stats().unwrap().entries(), 2);
1275 }
1276
1277 #[test]
1278 fn capacity_exhaustion_does_not_evict_an_active_entry() {
1279 let store = MemoryStore::with_clock(
1280 MemoryStoreConfig::new(1)
1281 .unwrap()
1282 .with_shard_count(1)
1283 .unwrap(),
1284 ManualClock::default(),
1285 );
1286 let policy = policy("auth.login", "client", 10, Duration::from_secs(60));
1287
1288 assert!(
1289 store
1290 .check(&Check::new(&policy, subject(1)))
1291 .unwrap()
1292 .is_allowed()
1293 );
1294 let denied = store.check(&Check::new(&policy, subject(2))).unwrap();
1295 assert!(!denied.is_allowed());
1296 assert_eq!(denied.retry_after(), Some(Duration::from_secs(60)));
1297 assert_eq!(store.stats().unwrap().entries(), 1);
1298 }
1299
1300 #[test]
1301 fn default_configuration_can_use_its_entire_capacity() {
1302 let store =
1303 MemoryStore::with_clock(MemoryStoreConfig::new(64).unwrap(), ManualClock::default());
1304 let policy = policy("auth.login", "client", 10, Duration::from_secs(60));
1305
1306 for byte in 0..64 {
1307 assert!(
1308 store
1309 .check(&Check::new(&policy, subject(byte)))
1310 .unwrap()
1311 .is_allowed()
1312 );
1313 }
1314
1315 let denied = store.check(&Check::new(&policy, subject(64))).unwrap();
1316 assert!(denied.is_denied());
1317 assert_eq!(store.stats().unwrap().entries(), 64);
1318 }
1319
1320 #[test]
1321 fn a_cross_shard_batch_preserves_input_order_and_updates_each_shard() {
1322 let store = MemoryStore::with_clock(
1323 MemoryStoreConfig::new(4)
1324 .unwrap()
1325 .with_shard_count(2)
1326 .unwrap(),
1327 ManualClock::default(),
1328 );
1329 let policy = policy("auth.login", "client", 10, Duration::from_secs(60));
1330 let shard_zero = subjects_for_shard(&store, &policy, 0, 1)[0];
1331 let shard_one = subjects_for_shard(&store, &policy, 1, 2);
1332 let checks = [
1333 Check::with_cost(&policy, shard_one[0], 2).unwrap(),
1334 Check::with_cost(&policy, shard_zero, 3).unwrap(),
1335 Check::with_cost(&policy, shard_one[1], 4).unwrap(),
1336 ];
1337
1338 assert_eq!(
1339 store.check_all(&checks),
1340 Ok(BatchDecision::allowed(vec![
1341 Decision::allowed(10, 8, Duration::from_secs(60)),
1342 Decision::allowed(10, 7, Duration::from_secs(60)),
1343 Decision::allowed(10, 6, Duration::from_secs(60)),
1344 ]))
1345 );
1346 assert_eq!(store.shards.shard(0).lock().unwrap().used(), 1);
1347 assert_eq!(store.shards.shard(1).lock().unwrap().used(), 2);
1348 }
1349
1350 #[test]
1351 fn a_full_shard_denies_a_batch_while_another_shard_has_room() {
1352 let store = MemoryStore::with_clock(
1353 MemoryStoreConfig::new(6)
1354 .unwrap()
1355 .with_shard_count(2)
1356 .unwrap(),
1357 ManualClock::default(),
1358 );
1359 let policy = policy("auth.login", "client", 10, Duration::from_secs(60));
1360 let crowded = subjects_for_shard(&store, &policy, 0, 4);
1361 let other = subjects_for_shard(&store, &policy, 1, 1)[0];
1362
1363 for key in &crowded[..2] {
1364 assert!(
1365 store
1366 .check(&Check::new(&policy, *key))
1367 .unwrap()
1368 .is_allowed()
1369 );
1370 }
1371 let checks = [
1372 Check::new(&policy, other),
1373 Check::new(&policy, crowded[2]),
1374 Check::new(&policy, crowded[3]),
1375 ];
1376
1377 assert_eq!(
1378 store.check_all(&checks),
1379 Ok(BatchDecision::denied(
1380 2,
1381 Denial::storage_capacity(Some(Duration::from_secs(60))),
1382 ))
1383 );
1384 assert_eq!(store.shards.shard(0).lock().unwrap().used(), 2);
1385 assert_eq!(store.shards.shard(1).lock().unwrap().used(), 0);
1386
1387 assert!(
1388 store
1389 .check(&Check::new(&policy, crowded[2]))
1390 .unwrap()
1391 .is_allowed()
1392 );
1393 assert!(
1394 store
1395 .check(&Check::new(&policy, other))
1396 .unwrap()
1397 .is_allowed()
1398 );
1399 }
1400
1401 #[test]
1402 fn an_unsatisfiable_per_shard_batch_returns_a_structural_error() {
1403 let store = MemoryStore::with_clock(
1404 MemoryStoreConfig::new(4)
1405 .unwrap()
1406 .with_shard_count(2)
1407 .unwrap(),
1408 ManualClock::default(),
1409 );
1410 let policy = policy("auth.login", "client", 2, Duration::from_secs(60));
1411 let keys = subjects_for_shard(&store, &policy, 0, 3);
1412 let other = subjects_for_shard(&store, &policy, 1, 1)[0];
1413 let other_check = Check::new(&policy, other);
1414 assert_eq!(
1415 store.check(&other_check),
1416 Ok(Decision::allowed(2, 1, Duration::from_secs(60)))
1417 );
1418 let checks = [
1419 other_check,
1420 Check::new(&policy, keys[0]),
1421 Check::new(&policy, keys[1]),
1422 Check::new(&policy, keys[2]),
1423 ];
1424
1425 assert_eq!(
1426 store.check_all(&checks),
1427 Err(MemoryStoreError::BatchExceedsShardCapacity {
1428 shard_index: 0,
1429 key_count: 3,
1430 capacity: 2,
1431 })
1432 );
1433 assert_eq!(store.stats().unwrap().entries(), 1);
1434 assert_eq!(
1435 store.check(&other_check),
1436 Ok(Decision::allowed(2, 0, Duration::from_secs(60)))
1437 );
1438 }
1439
1440 #[test]
1441 fn expiry_cleanup_is_bounded_and_capacity_remains_hard_bounded() {
1442 let clock = ManualClock::default();
1443 let config = MemoryStoreConfig::new(3)
1444 .unwrap()
1445 .with_shard_count(1)
1446 .unwrap()
1447 .with_max_expired_removals_per_check(1)
1448 .unwrap();
1449 let store = MemoryStore::with_clock(config, clock.clone());
1450 let policy = policy("auth.login", "client", 10, Duration::from_secs(1));
1451
1452 for byte in 1..=3 {
1453 assert!(
1454 store
1455 .check(&Check::new(&policy, subject(byte)))
1456 .unwrap()
1457 .is_allowed()
1458 );
1459 }
1460 clock.advance(Duration::from_secs(1));
1461
1462 assert!(
1463 store
1464 .check(&Check::new(&policy, subject(4)))
1465 .unwrap()
1466 .is_allowed()
1467 );
1468 assert_eq!(store.stats().unwrap().entries(), 3);
1469
1470 assert!(
1471 store
1472 .check(&Check::new(&policy, subject(5)))
1473 .unwrap()
1474 .is_allowed()
1475 );
1476 assert_eq!(store.stats().unwrap().entries(), 3);
1477 }
1478
1479 #[test]
1480 fn a_cross_shard_batch_attributes_cleanup_to_each_checks_target() {
1481 let clock = ManualClock::default();
1482 let store = MemoryStore::with_clock(
1483 MemoryStoreConfig::new(8)
1484 .unwrap()
1485 .with_shard_count(2)
1486 .unwrap()
1487 .with_max_expired_removals_per_check(1)
1488 .unwrap(),
1489 clock.clone(),
1490 );
1491 let policy = policy("auth.login", "client", 10, Duration::from_secs(1));
1492 let shard_zero = subjects_for_shard(&store, &policy, 0, 6);
1493 let shard_one = subjects_for_shard(&store, &policy, 1, 5);
1494
1495 for key in shard_zero[..4].iter().chain(&shard_one[..4]) {
1496 assert!(
1497 store
1498 .check(&Check::new(&policy, *key))
1499 .unwrap()
1500 .is_allowed()
1501 );
1502 }
1503 clock.advance(Duration::from_secs(1));
1504
1505 let checks = [
1506 Check::new(&policy, shard_zero[4]),
1507 Check::new(&policy, shard_one[4]),
1508 Check::new(&policy, shard_zero[5]),
1509 ];
1510 assert_eq!(
1511 store
1512 .check_all(&checks)
1513 .unwrap()
1514 .allowed_decisions()
1515 .map(<[Decision]>::len),
1516 Some(3),
1517 "the two checks targeting shard 0 need two cleanup slots"
1518 );
1519
1520 let shard = store.shards.shard(0).lock().unwrap();
1521 assert_eq!(shard.used(), 4);
1522 assert_eq!(shard.expiration_count_at_or_before(1_000), 2);
1523 drop(shard);
1524
1525 let shard = store.shards.shard(1).lock().unwrap();
1526 assert_eq!(shard.used(), 4);
1527 assert_eq!(shard.expiration_count_at_or_before(1_000), 3);
1528 }
1529
1530 #[test]
1531 fn an_atomic_batch_receives_the_cleanup_budget_for_each_check() {
1532 let clock = ManualClock::default();
1533 let config = MemoryStoreConfig::new(3)
1534 .unwrap()
1535 .with_shard_count(1)
1536 .unwrap()
1537 .with_max_expired_removals_per_check(1)
1538 .unwrap();
1539 let store = MemoryStore::with_clock(config, clock.clone());
1540 let policy = policy("auth.login", "client", 10, Duration::from_secs(1));
1541
1542 for byte in 1..=3 {
1543 assert!(
1544 store
1545 .check(&Check::new(&policy, subject(byte)))
1546 .unwrap()
1547 .is_allowed()
1548 );
1549 }
1550 clock.advance(Duration::from_secs(1));
1551
1552 let checks = [4, 5, 6].map(|byte| Check::new(&policy, subject(byte)));
1553 let result = store.check_all(&checks).unwrap();
1554 assert_eq!(result.allowed_decisions().map(<[Decision]>::len), Some(3));
1555 assert_eq!(store.stats().unwrap().entries(), 3);
1556 }
1557
1558 #[test]
1559 fn auxiliary_expiry_index_remains_bounded_across_many_windows() {
1560 let clock = ManualClock::default();
1561 let store = MemoryStore::with_clock(
1562 MemoryStoreConfig::new(1)
1563 .unwrap()
1564 .with_shard_count(1)
1565 .unwrap(),
1566 clock.clone(),
1567 );
1568 let policy = policy("auth.login", "client", 1, Duration::from_millis(1));
1569 let check = Check::new(&policy, subject(1));
1570
1571 for _ in 0..1_000 {
1572 assert!(store.check(&check).unwrap().is_allowed());
1573 clock.advance(Duration::from_millis(1));
1574 }
1575
1576 let shard = store.shards.shard(0).lock().unwrap();
1577 assert_eq!(shard.used(), 1);
1578 assert_eq!(shard.expiration_count(), 1);
1579 }
1580
1581 #[test]
1582 fn targeted_expired_refresh_keeps_indexes_aligned_for_single_and_batch() {
1583 for use_batch in [false, true] {
1584 let clock = ManualClock::default();
1585 let store = MemoryStore::with_clock(
1586 MemoryStoreConfig::new(2)
1587 .unwrap()
1588 .with_shard_count(1)
1589 .unwrap()
1590 .with_max_expired_removals_per_check(1)
1591 .unwrap(),
1592 clock.clone(),
1593 );
1594 let policy = policy("auth.login", "client", 10, Duration::from_millis(2));
1595 let earlier = Check::new(&policy, subject(1));
1596 let target = Check::new(&policy, subject(2));
1597
1598 assert!(store.check(&earlier).unwrap().is_allowed());
1599 clock.advance(Duration::from_millis(1));
1600 assert!(store.check(&target).unwrap().is_allowed());
1601 clock.advance(Duration::from_millis(2));
1602
1603 let decision = if use_batch {
1604 store
1605 .check_all(std::slice::from_ref(&target))
1606 .unwrap()
1607 .try_into_single_decision()
1608 .expect("a one-element batch returns one decision")
1609 } else {
1610 store.check(&target).unwrap()
1611 };
1612 assert_eq!(decision, Decision::allowed(10, 9, Duration::from_millis(2)));
1613
1614 let key = target.counter_key();
1615 let shard = store.shards.shard(0).lock().unwrap();
1616 assert_eq!(shard.used(), 1);
1617 assert_eq!(shard.expiration_count(), 1);
1618 assert_eq!(shard.entry(key), Some((&Entry { used: 1 }, 5)));
1619 assert!(shard.contains_expiration(key, 5));
1620 }
1621 }
1622
1623 #[test]
1624 fn a_denied_batch_does_not_consume_other_checks() {
1625 let store = MemoryStore::with_clock(
1626 MemoryStoreConfig::new(8)
1627 .unwrap()
1628 .with_shard_count(1)
1629 .unwrap(),
1630 ManualClock::default(),
1631 );
1632 let exhausted = policy("auth.login", "client", 1, Duration::from_secs(60));
1633 let untouched = policy("auth.login", "identity", 1, Duration::from_secs(60));
1634 let exhausted_check = Check::new(&exhausted, subject(1));
1635 let untouched_check = Check::new(&untouched, subject(2));
1636
1637 assert!(store.check(&exhausted_check).unwrap().is_allowed());
1638 let result = store
1639 .check_all(&[exhausted_check, untouched_check])
1640 .unwrap();
1641 assert!(result.is_enforced_denial());
1642 assert_eq!(result.denied_index(), Some(0));
1643
1644 assert!(
1645 store
1646 .check(&Check::new(&untouched, subject(2)))
1647 .unwrap()
1648 .is_allowed()
1649 );
1650 }
1651
1652 #[test]
1653 fn duplicate_keys_are_rejected_before_consumption() {
1654 let store =
1655 MemoryStore::with_clock(MemoryStoreConfig::new(8).unwrap(), ManualClock::default());
1656 let alpha = policy("auth.alpha", "client", 2, Duration::from_secs(60));
1657 let beta = policy("auth.beta", "client", 2, Duration::from_secs(60));
1658 let checks = [
1659 Check::new(&beta, subject(1)),
1660 Check::new(&beta, subject(1)),
1661 Check::new(&alpha, subject(2)),
1662 Check::new(&alpha, subject(2)),
1663 ];
1664
1665 assert_eq!(
1666 store.check_all(&checks),
1667 Err(MemoryStoreError::InvalidBatch(BatchError::DuplicateKey {
1668 first_index: 0,
1669 duplicate_index: 1,
1670 }))
1671 );
1672 assert_eq!(store.stats().unwrap().entries(), 0);
1673 }
1674
1675 #[test]
1676 fn concurrent_checks_never_over_admit() {
1677 let store = Arc::new(MemoryStore::with_clock(
1678 MemoryStoreConfig::new(8).unwrap(),
1679 ManualClock::default(),
1680 ));
1681 let policy = Arc::new(policy("auth.login", "client", 25, Duration::from_secs(60)));
1682
1683 let allowed = (0..100)
1684 .map(|_| {
1685 let store = Arc::clone(&store);
1686 let policy = Arc::clone(&policy);
1687 thread::spawn(move || {
1688 store
1689 .check(&Check::new(&policy, subject(1)))
1690 .unwrap()
1691 .is_allowed()
1692 })
1693 })
1694 .map(|thread| usize::from(thread.join().unwrap()))
1695 .sum::<usize>();
1696
1697 assert_eq!(allowed, 25);
1698 }
1699
1700 #[test]
1701 fn concurrent_cross_shard_batches_lock_consistently_and_never_over_admit() {
1702 const THREAD_COUNT: usize = 8;
1703 const CALLS_PER_THREAD: usize = 64;
1704
1705 let store = MemoryStore::with_clock(
1706 MemoryStoreConfig::new(2)
1707 .unwrap()
1708 .with_shard_count(2)
1709 .unwrap(),
1710 ManualClock::default(),
1711 );
1712 let limit = u64::try_from(THREAD_COUNT * CALLS_PER_THREAD).unwrap();
1713 let policy = policy("auth.login", "client", limit, Duration::from_secs(60));
1714 let first = subjects_for_shard(&store, &policy, 0, 1)[0];
1715 let second = subjects_for_shard(&store, &policy, 1, 1)[0];
1716 let store = Arc::new(store);
1717 let policy = Arc::new(policy);
1718 let barrier = Arc::new(Barrier::new(THREAD_COUNT));
1719 let (finished_sender, finished_receiver) = mpsc::channel();
1720
1721 let threads = (0..THREAD_COUNT)
1722 .map(|thread_index| {
1723 let store = Arc::clone(&store);
1724 let policy = Arc::clone(&policy);
1725 let barrier = Arc::clone(&barrier);
1726 let finished_sender = finished_sender.clone();
1727 thread::spawn(move || {
1728 for call_index in 0..CALLS_PER_THREAD {
1729 barrier.wait();
1730 let subjects = if (thread_index + call_index) % 2 == 0 {
1731 [first, second]
1732 } else {
1733 [second, first]
1734 };
1735 let checks = subjects.map(|subject| Check::new(policy.as_ref(), subject));
1736 let result = store.check_all(&checks).unwrap();
1737 assert!(
1738 result
1739 .allowed_decisions()
1740 .is_some_and(|decisions| decisions.len() == checks.len()),
1741 "every call through the configured limit must be allowed: {result:?}"
1742 );
1743 }
1744 finished_sender.send(()).unwrap();
1745 })
1746 })
1747 .collect::<Vec<_>>();
1748 drop(finished_sender);
1749
1750 for _ in 0..THREAD_COUNT {
1751 finished_receiver
1752 .recv_timeout(Duration::from_secs(5))
1753 .expect("cross-shard batches must not deadlock");
1754 }
1755 for thread in threads {
1756 thread.join().unwrap();
1757 }
1758
1759 assert_eq!(store.stats().unwrap().entries(), 2);
1760 for key in [first, second] {
1761 assert_eq!(
1762 store.check(&Check::new(policy.as_ref(), key)),
1763 Ok(Decision::denied(quota(limit, Duration::from_secs(60))))
1764 );
1765 }
1766 }
1767
1768 #[test]
1769 fn a_poisoned_default_shard_remains_fail_closed() {
1770 let clock = PanicOnceClock::default();
1771 let store = MemoryStore::with_clock(
1772 MemoryStoreConfig::new(1)
1773 .unwrap()
1774 .with_shard_count(1)
1775 .unwrap(),
1776 clock.clone(),
1777 );
1778 let policy = policy("auth.login", "client", 1, Duration::from_secs(60));
1779 let exhausted = Check::new(&policy, subject(1));
1780 let new_key = Check::new(&policy, subject(2));
1781
1782 assert!(store.check(&exhausted).unwrap().is_allowed());
1783 clock.panic_once();
1784 let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
1785 let _ = store.check(&new_key);
1786 }));
1787 assert!(panic_result.is_err());
1788
1789 let poisoned = Err(MemoryStoreError::PoisonedShard { shard_index: 0 });
1790 assert_eq!(store.check(&exhausted), poisoned);
1791 assert_eq!(store.check(&new_key), poisoned);
1792 assert_eq!(store.check(&exhausted), poisoned);
1793 assert_eq!(
1794 store.stats(),
1795 Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1796 );
1797 assert_eq!(
1798 store.clear(),
1799 Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1800 );
1801 }
1802
1803 #[test]
1804 fn batch_preflight_preserves_validation_capacity_and_lock_precedence() {
1805 let clock = PanicOnceClock::default();
1806 let store = MemoryStore::with_clock(
1807 MemoryStoreConfig::new(1)
1808 .unwrap()
1809 .with_shard_count(1)
1810 .unwrap()
1811 .with_max_batch_size(2)
1812 .unwrap(),
1813 clock.clone(),
1814 );
1815 let policy = policy("auth.preflight", "client", 1, Duration::from_secs(60));
1816 let checks = [
1817 Check::new(&policy, subject(1)),
1818 Check::new(&policy, subject(2)),
1819 Check::new(&policy, subject(3)),
1820 ];
1821
1822 clock.panic_once();
1823 let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
1824 let _ = store.check(&checks[0]);
1825 }));
1826 assert!(panic_result.is_err());
1827
1828 assert_eq!(store.check_all(&[]), Ok(BatchDecision::allowed(Vec::new())));
1829 assert_eq!(
1830 store.check_all(&[checks[0], checks[0]]),
1831 Err(MemoryStoreError::InvalidBatch(BatchError::DuplicateKey {
1832 first_index: 0,
1833 duplicate_index: 1,
1834 }))
1835 );
1836 assert_eq!(
1837 store.check_all(&checks),
1838 Err(MemoryStoreError::InvalidBatch(BatchError::BatchTooLarge {
1839 actual: 3,
1840 maximum: 2,
1841 }))
1842 );
1843 assert_eq!(
1844 store.check_all(&checks[..2]),
1845 Err(MemoryStoreError::BatchExceedsShardCapacity {
1846 shard_index: 0,
1847 key_count: 2,
1848 capacity: 1,
1849 })
1850 );
1851 assert_eq!(
1852 store.check_all(&checks[..1]),
1853 Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1854 );
1855 }
1856
1857 #[test]
1858 fn failed_checks_keep_policy_metadata_but_failed_batches_remain_anonymous() {
1859 let clock = PanicOnceClock::default();
1860 let observer = Arc::new(AdmissionMetadataObserver::default());
1861 let store = MemoryStore::with_clock(
1862 MemoryStoreConfig::new(1)
1863 .unwrap()
1864 .with_shard_count(1)
1865 .unwrap(),
1866 clock.clone(),
1867 )
1868 .with_observer(observer.clone());
1869 let policy = policy(
1870 "auth.observed-failure",
1871 "client",
1872 1,
1873 Duration::from_secs(60),
1874 );
1875 let check = Check::new(&policy, subject(1));
1876
1877 clock.panic_once();
1878 let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
1879 let _ = store.check(&check);
1880 }));
1881 assert!(panic_result.is_err());
1882 assert_eq!(
1883 store.check(&check),
1884 Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1885 );
1886 assert_eq!(
1887 store.check_all(&[check]),
1888 Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1889 );
1890
1891 assert_eq!(
1892 observer.admissions.lock().unwrap().as_slice(),
1893 [
1894 RecordedAdmissionMetadata {
1895 operation: AdmissionOperation::Check,
1896 batch_size: 1,
1897 has_policy_id: true,
1898 has_scope_id: true,
1899 has_policy_fingerprint: true,
1900 outcome: AdmissionOutcome::Failed,
1901 consumption: ConsumptionStatus::NotConsumed,
1902 },
1903 RecordedAdmissionMetadata {
1904 operation: AdmissionOperation::Batch,
1905 batch_size: 1,
1906 has_policy_id: false,
1907 has_scope_id: false,
1908 has_policy_fingerprint: false,
1909 outcome: AdmissionOutcome::Failed,
1910 consumption: ConsumptionStatus::NotConsumed,
1911 },
1912 ]
1913 );
1914 }
1915
1916 #[test]
1917 fn explicit_recovery_resets_only_poisoned_shards_behind_an_arc() {
1918 let clock = PanicOnceClock::default();
1919 let store = Arc::new(MemoryStore::with_clock(
1920 MemoryStoreConfig::new(4)
1921 .unwrap()
1922 .with_shard_count(2)
1923 .unwrap(),
1924 clock.clone(),
1925 ));
1926 let policy = policy("auth.login", "client", 1, Duration::from_secs(60));
1927 let reset_subject = subjects_for_shard(&store, &policy, 0, 1)[0];
1928 let retained_subject = subjects_for_shard(&store, &policy, 1, 1)[0];
1929 let reset_check = Check::new(&policy, reset_subject);
1930 let retained_check = Check::new(&policy, retained_subject);
1931
1932 assert!(store.check(&reset_check).unwrap().is_allowed());
1933 assert!(store.check(&retained_check).unwrap().is_allowed());
1934 clock.panic_once();
1935 let panicked_store = Arc::clone(&store);
1936 let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(move || {
1937 let _ = panicked_store.check(&reset_check);
1938 }));
1939 assert!(panic_result.is_err());
1940
1941 assert_eq!(
1942 store.check(&reset_check),
1943 Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1944 );
1945 assert!(store.check(&retained_check).unwrap().is_denied());
1946 assert!(format!("{store:?}").contains("poisoned_shards: 1"));
1947
1948 assert_eq!(store.recover_poisoned(), 1);
1949 assert_eq!(
1950 store.recover_poisoned(),
1951 0,
1952 "recovery must be idempotent when no new panic occurs"
1953 );
1954 assert_eq!(store.stats().unwrap().entries(), 1);
1955 assert!(
1956 store.check(&reset_check).unwrap().is_allowed(),
1957 "the recovered shard starts with empty quota state"
1958 );
1959 assert!(
1960 store.check(&retained_check).unwrap().is_denied(),
1961 "healthy-shard quota state must survive recovery"
1962 );
1963 assert!(format!("{store:?}").contains("poisoned_shards: 0"));
1964 }
1965
1966 #[test]
1967 fn recovery_reopens_every_shard_poisoned_by_an_unwinding_batch() {
1968 let clock = PanicOnceClock::default();
1969 let store = Arc::new(MemoryStore::with_clock(
1970 MemoryStoreConfig::new(2)
1971 .unwrap()
1972 .with_shard_count(2)
1973 .unwrap(),
1974 clock.clone(),
1975 ));
1976 let policy = policy("auth.login", "client", 1, Duration::from_secs(60));
1977 let shard_zero = subjects_for_shard(&store, &policy, 0, 1)[0];
1978 let shard_one = subjects_for_shard(&store, &policy, 1, 1)[0];
1979 let checks = [
1980 Check::new(&policy, shard_one),
1981 Check::new(&policy, shard_zero),
1982 ];
1983
1984 clock.panic_once();
1985 let panicked_store = Arc::clone(&store);
1986 let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(move || {
1987 let _ = panicked_store.check_all(&checks);
1988 }));
1989 assert!(panic_result.is_err());
1990 assert_eq!(
1991 store.check(&checks[0]),
1992 Err(MemoryStoreError::PoisonedShard { shard_index: 1 })
1993 );
1994 assert_eq!(
1995 store.check(&checks[1]),
1996 Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1997 );
1998
1999 assert_eq!(store.recover_poisoned(), 2);
2000 assert_eq!(store.stats().unwrap().entries(), 0);
2001 assert!(
2002 store
2003 .check_all(&checks)
2004 .unwrap()
2005 .allowed_decisions()
2006 .is_some_and(|decisions| decisions.len() == 2),
2007 "all shards must be usable after one atomic recovery"
2008 );
2009 }
2010}