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