1use std::{
2 collections::{
3 BTreeSet, HashMap,
4 hash_map::{Entry as MapEntry, RandomState},
5 },
6 hash::BuildHasher,
7 sync::{Mutex, MutexGuard},
8 time::Duration,
9};
10
11use runlimit_core::{
12 BatchDecision, BatchError, Check, CounterKey, Decision, Denial, 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(Debug)]
31struct Shard {
32 capacity: usize,
33 latest_observed_millis: u128,
34 entries: HashMap<CounterKey, Entry>,
35 expirations: BTreeSet<Expiration>,
36}
37
38impl Shard {
39 fn new(capacity: usize) -> Self {
40 Self {
41 capacity,
42 latest_observed_millis: 0,
43 entries: HashMap::new(),
44 expirations: BTreeSet::new(),
45 }
46 }
47
48 fn clear(&mut self) {
49 self.entries.clear();
50 self.expirations.clear();
51 }
52
53 fn prune_expired(&mut self, now_millis: u128, maximum: usize) {
54 for _ in 0..maximum {
55 let Some(expiration) = self.expirations.first() else {
56 break;
57 };
58 if expiration.expires_at_millis > now_millis {
59 break;
60 }
61
62 let expiration = self
63 .expirations
64 .pop_first()
65 .expect("the first expiration was present");
66 let removed = self.entries.remove(&expiration.key);
67 debug_assert_eq!(
68 removed.map(|entry| entry.expires_at_millis),
69 Some(expiration.expires_at_millis),
70 "the entry and expiration indexes diverged"
71 );
72 }
73 }
74
75 fn capacity_retry_after(&self, now_millis: u128) -> Option<Duration> {
76 self.expirations.first().map(|expiration| {
77 duration_from_millis(
78 expiration
79 .expires_at_millis
80 .saturating_sub(now_millis)
81 .max(1),
82 )
83 })
84 }
85
86 fn quota_denial(&self, check: &PreparedCheck, now_millis: u128) -> Option<Denial> {
87 let entry = self
88 .entries
89 .get(&check.counter_key)
90 .filter(|entry| entry.expires_at_millis > now_millis)?;
91 (check.cost > check.limit - entry.used).then(|| Denial::QuotaExceeded {
92 limit: check.limit,
93 retry_after: duration_from_millis(entry.expires_at_millis.saturating_sub(now_millis)),
94 })
95 }
96
97 fn consume(&mut self, check: &PreparedCheck, now_millis: u128) -> Decision {
98 let expires_at_millis = now_millis + u128::from(check.window_millis);
99 let fresh_entry = Entry {
100 used: check.cost,
101 expires_at_millis,
102 };
103 let fresh_expiration = Expiration {
104 expires_at_millis,
105 key: check.counter_key,
106 };
107
108 match self.entries.entry(check.counter_key) {
109 MapEntry::Occupied(mut occupied) => {
110 if occupied.get().expires_at_millis > now_millis {
111 let entry = occupied.get_mut();
112 entry.used += check.cost;
113 return Decision::allowed(
114 check.limit,
115 check.limit - entry.used,
116 duration_from_millis(entry.expires_at_millis.saturating_sub(now_millis)),
117 );
118 }
119
120 let expired = *occupied.get();
121 let removed = self.expirations.remove(&Expiration {
122 expires_at_millis: expired.expires_at_millis,
123 key: check.counter_key,
124 });
125 debug_assert!(removed, "an expired entry must have an expiration");
126 let replaced = occupied.insert(fresh_entry);
127 debug_assert_eq!(replaced, expired);
128 }
129 MapEntry::Vacant(vacant) => {
130 vacant.insert(fresh_entry);
131 }
132 }
133
134 let inserted = self.expirations.insert(fresh_expiration);
135 debug_assert!(inserted, "an inserted entry must have one expiration");
136 Decision::allowed(
137 check.limit,
138 check.limit - check.cost,
139 duration_from_millis(expires_at_millis.saturating_sub(now_millis)),
140 )
141 }
142}
143
144#[derive(Debug)]
145struct PreparedCheck {
146 input_index: usize,
147 counter_key: CounterKey,
148 shard_index: usize,
149 shard_position: usize,
150 limit: u64,
151 window_millis: u64,
152 cost: u64,
153}
154
155impl PreparedCheck {
156 fn new(input_index: usize, check: &Check<'_>, shard_index: usize) -> Self {
157 Self {
158 input_index,
159 counter_key: check.counter_key(),
160 shard_index,
161 shard_position: 0,
162 limit: check.policy().limit(),
163 window_millis: check.policy().window_millis(),
164 cost: check.cost(),
165 }
166 }
167}
168
169pub struct MemoryStore<C = SystemClock> {
181 config: MemoryStoreConfig,
182 clock: C,
183 shard_hasher: RandomState,
184 shards: Box<[Mutex<Shard>]>,
185}
186
187impl MemoryStore<SystemClock> {
188 pub fn new(config: MemoryStoreConfig) -> Self {
190 Self::with_clock(config, SystemClock::new())
191 }
192}
193
194impl<C: Clock> MemoryStore<C> {
195 pub fn with_clock(config: MemoryStoreConfig, clock: C) -> Self {
199 let shards = (0..config.shard_count())
200 .map(|index| Mutex::new(Shard::new(config.shard_capacity(index))))
201 .collect::<Vec<_>>()
202 .into_boxed_slice();
203
204 Self {
205 config,
206 clock,
207 shard_hasher: RandomState::new(),
208 shards,
209 }
210 }
211
212 pub fn check(&self, check: &Check<'_>) -> Result<Decision, MemoryStoreError> {
219 let counter_key = check.counter_key();
220 let shard_index = self.shard_index(&counter_key);
221 let prepared = PreparedCheck::new(0, check, shard_index);
222 let mut shard = self.lock_shard(shard_index)?;
223 let observed_millis = self.clock.now().as_millis();
224 let now_millis = observed_millis.max(shard.latest_observed_millis);
225 shard.latest_observed_millis = now_millis;
226 shard.prune_expired(now_millis, self.config.max_expired_removals_per_check());
227
228 if let Some(denial) = shard.quota_denial(&prepared, now_millis) {
229 return Ok(Decision::denied(denial));
230 }
231 if !shard.entries.contains_key(&counter_key) && shard.entries.len() >= shard.capacity {
232 return Ok(Decision::denied(Denial::StorageCapacity {
233 retry_after: shard.capacity_retry_after(now_millis),
234 }));
235 }
236
237 Ok(shard.consume(&prepared, now_millis))
238 }
239
240 #[allow(clippy::too_many_lines)]
252 pub fn check_all(&self, checks: &[Check<'_>]) -> Result<BatchDecision, MemoryStoreError> {
253 validate_batch(checks, self.config.max_batch_size())?;
254 if checks.is_empty() {
255 return Ok(BatchDecision::Allowed(Vec::new()));
256 }
257
258 let mut prepared = Vec::with_capacity(checks.len());
259 for (input_index, check) in checks.iter().enumerate() {
260 let counter_key = check.counter_key();
261 prepared.push(PreparedCheck::new(
262 input_index,
263 check,
264 self.shard_index(&counter_key),
265 ));
266 }
267
268 let mut shard_indexes = prepared
269 .iter()
270 .map(|check| check.shard_index)
271 .collect::<Vec<_>>();
272 shard_indexes.sort_unstable();
273 shard_indexes.dedup();
274 for check in &mut prepared {
275 check.shard_position =
276 shard_indexes.partition_point(|index| *index < check.shard_index);
277 debug_assert_eq!(
278 shard_indexes.get(check.shard_position),
279 Some(&check.shard_index)
280 );
281 }
282
283 let mut locked_shards = self.lock_shards(&shard_indexes)?;
284 let observed_millis = self.clock.now().as_millis();
285 let now_millis = locked_shards
286 .iter()
287 .map(|(_, shard)| shard.latest_observed_millis)
288 .fold(observed_millis, u128::max);
289 let mut checks_per_shard = vec![0_usize; locked_shards.len()];
290 for check in &prepared {
291 checks_per_shard[check.shard_position] += 1;
292 }
293 for ((_, shard), check_count) in locked_shards.iter_mut().zip(checks_per_shard) {
294 shard.latest_observed_millis = now_millis;
295 let cleanup_limit = self
296 .config
297 .max_expired_removals_per_check()
298 .saturating_mul(check_count);
299 shard.prune_expired(now_millis, cleanup_limit);
300 }
301
302 let mut pending_insertions = vec![0_usize; locked_shards.len()];
303 for check in &prepared {
304 let shard = &locked_shards[check.shard_position].1;
305 if let Some(denial) = shard.quota_denial(check, now_millis) {
306 return Ok(BatchDecision::Denied {
307 index: check.input_index,
308 denial,
309 });
310 }
311
312 if !shard.entries.contains_key(&check.counter_key) {
313 let projected_len = shard.entries.len() + pending_insertions[check.shard_position];
314 if projected_len >= shard.capacity {
315 return Ok(BatchDecision::Denied {
316 index: check.input_index,
317 denial: Denial::StorageCapacity {
318 retry_after: shard.capacity_retry_after(now_millis),
319 },
320 });
321 }
322 pending_insertions[check.shard_position] += 1;
323 }
324 }
325
326 let mut decisions = Vec::with_capacity(prepared.len());
327 for check in &prepared {
328 let shard = &mut locked_shards[check.shard_position].1;
329 decisions.push(shard.consume(check, now_millis));
330 }
331
332 Ok(BatchDecision::Allowed(decisions))
333 }
334
335 pub fn stats(&self) -> Result<MemoryStoreStats, MemoryStoreError> {
341 let shard_indexes = (0..self.shards.len()).collect::<Vec<_>>();
342 let locked_shards = self.lock_shards(&shard_indexes)?;
343 Ok(MemoryStoreStats {
344 entries: locked_shards
345 .iter()
346 .map(|(_, shard)| shard.entries.len())
347 .sum(),
348 capacity: self.config.max_keys(),
349 shard_count: self.config.shard_count(),
350 })
351 }
352
353 pub fn clear(&self) -> Result<(), MemoryStoreError> {
359 let shard_indexes = (0..self.shards.len()).collect::<Vec<_>>();
360 let mut locked_shards = self.lock_shards(&shard_indexes)?;
361 for (_, shard) in &mut locked_shards {
362 shard.clear();
363 }
364 Ok(())
365 }
366
367 fn shard_index(&self, key: &CounterKey) -> usize {
368 #[allow(clippy::cast_possible_truncation)]
369 let hash = self.shard_hasher.hash_one(key) as usize;
370 hash % self.shards.len()
371 }
372
373 fn lock_shard(&self, index: usize) -> Result<MutexGuard<'_, Shard>, MemoryStoreError> {
374 self.shards[index]
375 .lock()
376 .map_err(|_| MemoryStoreError::PoisonedShard { shard_index: index })
377 }
378
379 fn lock_shards<'a>(
380 &'a self,
381 indexes: &[usize],
382 ) -> Result<Vec<(usize, MutexGuard<'a, Shard>)>, MemoryStoreError> {
383 let mut locked = Vec::with_capacity(indexes.len());
384 for &index in indexes {
385 locked.push((index, self.lock_shard(index)?));
386 }
387 Ok(locked)
388 }
389}
390
391fn duration_from_millis(millis: u128) -> Duration {
392 Duration::from_millis(
393 u64::try_from(millis)
394 .expect("a counter's remaining duration cannot exceed its portable policy window"),
395 )
396}
397
398#[derive(Clone, Copy, Debug, Eq, PartialEq)]
400pub struct MemoryStoreStats {
401 entries: usize,
402 capacity: usize,
403 shard_count: usize,
404}
405
406impl MemoryStoreStats {
407 pub const fn entries(self) -> usize {
409 self.entries
410 }
411
412 pub const fn capacity(self) -> usize {
414 self.capacity
415 }
416
417 pub const fn shard_count(self) -> usize {
419 self.shard_count
420 }
421}
422
423#[derive(Clone, Debug, Error, Eq, PartialEq)]
425pub enum MemoryStoreError {
426 #[error(transparent)]
428 InvalidBatch(#[from] BatchError),
429 #[error("memory-store shard {shard_index} is poisoned and unavailable")]
431 PoisonedShard {
432 shard_index: usize,
434 },
435}
436
437#[cfg(test)]
438mod tests {
439 use std::{
440 sync::{
441 Arc, Mutex,
442 atomic::{AtomicBool, AtomicU64, Ordering},
443 },
444 thread,
445 time::Duration,
446 };
447
448 use runlimit_core::{
449 BatchDecision, BatchError, Check, Decision, Denial, FixedWindowPolicy, MAX_LIMIT,
450 MAX_WINDOW, MAX_WINDOW_MILLIS, PolicyId, ScopeId, SubjectKey,
451 };
452
453 use super::{Entry, Expiration, MemoryStore, MemoryStoreError};
454 use crate::{Clock, MemoryStoreConfig};
455
456 #[derive(Clone, Default)]
457 struct ManualClock {
458 now_millis: Arc<AtomicU64>,
459 }
460
461 impl ManualClock {
462 fn advance(&self, duration: Duration) {
463 let millis = u64::try_from(duration.as_millis()).unwrap();
464 self.now_millis.fetch_add(millis, Ordering::Relaxed);
465 }
466
467 fn set(&self, duration: Duration) {
468 let millis = u64::try_from(duration.as_millis()).unwrap();
469 self.now_millis.store(millis, Ordering::Relaxed);
470 }
471 }
472
473 impl Clock for ManualClock {
474 fn now(&self) -> Duration {
475 Duration::from_millis(self.now_millis.load(Ordering::Relaxed))
476 }
477 }
478
479 #[derive(Clone, Default)]
480 struct PanicOnceClock {
481 panic_next: Arc<AtomicBool>,
482 }
483
484 impl PanicOnceClock {
485 fn panic_once(&self) {
486 self.panic_next.store(true, Ordering::Relaxed);
487 }
488 }
489
490 impl Clock for PanicOnceClock {
491 fn now(&self) -> Duration {
492 assert!(
493 !self.panic_next.swap(false, Ordering::Relaxed),
494 "panic from test clock"
495 );
496 Duration::ZERO
497 }
498 }
499
500 #[derive(Clone)]
501 struct WideManualClock {
502 now_millis: Arc<Mutex<u128>>,
503 }
504
505 impl WideManualClock {
506 fn new(now_millis: u128) -> Self {
507 Self {
508 now_millis: Arc::new(Mutex::new(now_millis)),
509 }
510 }
511
512 fn advance(&self, millis: u128) {
513 let mut now_millis = self.now_millis.lock().unwrap();
514 *now_millis += millis;
515 }
516 }
517
518 impl Clock for WideManualClock {
519 fn now(&self) -> Duration {
520 let millis = *self.now_millis.lock().unwrap();
521 let seconds = u64::try_from(millis / 1_000).unwrap();
522 let subsec_millis = u32::try_from(millis % 1_000).unwrap();
523 Duration::new(seconds, subsec_millis * 1_000_000)
524 }
525 }
526
527 fn policy(policy_id: &str, scope_id: &str, limit: u64, window: Duration) -> FixedWindowPolicy {
528 FixedWindowPolicy::new(
529 PolicyId::new(policy_id).unwrap(),
530 ScopeId::new(scope_id).unwrap(),
531 limit,
532 window,
533 )
534 .unwrap()
535 }
536
537 fn subject(byte: u8) -> SubjectKey {
538 SubjectKey::from_digest([byte; 32])
539 }
540
541 #[test]
542 fn enforces_quota_and_reports_exact_retry_duration() {
543 let clock = ManualClock::default();
544 let store = MemoryStore::with_clock(MemoryStoreConfig::new(8).unwrap(), clock.clone());
545 let policy = policy("auth.login", "client", 2, Duration::from_secs(60));
546 let check = Check::new(&policy, subject(1));
547
548 let first = store.check(&check).unwrap();
549 assert!(first.is_allowed());
550 assert_eq!(first.remaining(), Some(1));
551 assert_eq!(first.retry_after(), None);
552
553 let second = store.check(&check).unwrap();
554 assert!(second.is_allowed());
555 assert_eq!(second.remaining(), Some(0));
556
557 let denied = store.check(&check).unwrap();
558 assert!(!denied.is_allowed());
559 assert_eq!(denied.retry_after(), Some(Duration::from_secs(60)));
560
561 clock.advance(Duration::from_secs(10));
562 assert_eq!(
563 store.check(&check).unwrap().retry_after(),
564 Some(Duration::from_secs(50))
565 );
566
567 clock.advance(Duration::from_secs(50));
568 let reset = store.check(&check).unwrap();
569 assert!(reset.is_allowed());
570 assert_eq!(reset.remaining(), Some(1));
571 assert_eq!(reset.reset_after(), Some(Duration::from_secs(60)));
572 }
573
574 #[test]
575 fn single_check_matches_a_one_element_batch_across_state_transitions() {
576 #[derive(Clone, Copy)]
577 struct Step {
578 now: Duration,
579 subject: u8,
580 cost: u64,
581 expected: Decision,
582 }
583
584 let config = MemoryStoreConfig::new(2)
585 .unwrap()
586 .with_shard_count(1)
587 .unwrap()
588 .with_max_expired_removals_per_check(1)
589 .unwrap();
590 let single_clock = ManualClock::default();
591 let batch_clock = ManualClock::default();
592 let single_store = MemoryStore::with_clock(config.clone(), single_clock.clone());
593 let batch_store = MemoryStore::with_clock(config, batch_clock.clone());
594 let policy = policy("auth.login", "client", 5, Duration::from_millis(10));
595 let steps = [
596 Step {
597 now: Duration::ZERO,
598 subject: 1,
599 cost: 2,
600 expected: Decision::allowed(5, 3, Duration::from_millis(10)),
601 },
602 Step {
603 now: Duration::from_millis(3),
604 subject: 1,
605 cost: 2,
606 expected: Decision::allowed(5, 1, Duration::from_millis(7)),
607 },
608 Step {
609 now: Duration::from_millis(3),
610 subject: 1,
611 cost: 2,
612 expected: Decision::denied(Denial::QuotaExceeded {
613 limit: 5,
614 retry_after: Duration::from_millis(7),
615 }),
616 },
617 Step {
618 now: Duration::from_millis(9),
619 subject: 1,
620 cost: 1,
621 expected: Decision::allowed(5, 0, Duration::from_millis(1)),
622 },
623 Step {
624 now: Duration::from_millis(10),
625 subject: 1,
626 cost: 3,
627 expected: Decision::allowed(5, 2, Duration::from_millis(10)),
628 },
629 Step {
630 now: Duration::from_millis(8),
631 subject: 1,
632 cost: 1,
633 expected: Decision::allowed(5, 1, Duration::from_millis(10)),
634 },
635 Step {
636 now: Duration::from_millis(10),
637 subject: 2,
638 cost: 1,
639 expected: Decision::allowed(5, 4, Duration::from_millis(10)),
640 },
641 Step {
642 now: Duration::from_millis(10),
643 subject: 3,
644 cost: 1,
645 expected: Decision::denied(Denial::StorageCapacity {
646 retry_after: Some(Duration::from_millis(10)),
647 }),
648 },
649 Step {
650 now: Duration::from_millis(20),
651 subject: 3,
652 cost: 1,
653 expected: Decision::allowed(5, 4, Duration::from_millis(10)),
654 },
655 ];
656
657 for (index, step) in steps.into_iter().enumerate() {
658 single_clock.set(step.now);
659 batch_clock.set(step.now);
660 let check = Check::with_cost(&policy, subject(step.subject), step.cost).unwrap();
661
662 let single = single_store.check(&check).unwrap();
663 let batch = batch_store
664 .check_all(std::slice::from_ref(&check))
665 .unwrap()
666 .try_into_single_decision()
667 .expect("a one-element batch returns one decision");
668
669 assert_eq!(single, batch, "step {index}");
670 assert_eq!(single, step.expected, "step {index}");
671 }
672
673 assert_eq!(single_store.stats().unwrap(), batch_store.stats().unwrap());
674 }
675
676 #[test]
677 fn windows_remain_exact_across_the_u64_millisecond_boundary() {
678 let clock = WideManualClock::new(u128::from(u64::MAX));
679 let store = MemoryStore::with_clock(MemoryStoreConfig::new(1).unwrap(), clock.clone());
680 let policy = policy("auth.login", "client", MAX_LIMIT, MAX_WINDOW);
681 let check = Check::with_cost(&policy, subject(1), MAX_LIMIT).unwrap();
682
683 let first = store.check(&check).unwrap();
684 assert!(first.is_allowed());
685 assert_eq!(first.remaining(), Some(0));
686 assert_eq!(first.reset_after(), Some(MAX_WINDOW));
687
688 let denied = store.check(&check).unwrap();
689 assert!(denied.is_denied());
690 assert_eq!(denied.retry_after(), Some(MAX_WINDOW));
691
692 clock.advance(u128::from(MAX_WINDOW_MILLIS - 1));
693 let nearly_reset = store.check(&check).unwrap();
694 assert!(nearly_reset.is_denied());
695 assert_eq!(nearly_reset.retry_after(), Some(Duration::from_millis(1)));
696
697 clock.advance(1);
698 let reset = store.check(&check).unwrap();
699 assert!(reset.is_allowed());
700 assert_eq!(reset.reset_after(), Some(MAX_WINDOW));
701 }
702
703 #[test]
704 fn policy_configuration_changes_use_independent_counters() {
705 let store = MemoryStore::with_clock(
706 MemoryStoreConfig::new(2)
707 .unwrap()
708 .with_shard_count(1)
709 .unwrap(),
710 ManualClock::default(),
711 );
712 let strict = policy("auth.login", "client", 1, Duration::from_secs(60));
713 let relaxed = policy("auth.login", "client", 2, Duration::from_secs(60));
714 let key = subject(1);
715
716 assert!(store.check(&Check::new(&strict, key)).unwrap().is_allowed());
717 assert!(
718 store
719 .check(&Check::new(&relaxed, key))
720 .unwrap()
721 .is_allowed()
722 );
723 assert_eq!(store.stats().unwrap().entries(), 2);
724 }
725
726 #[test]
727 fn capacity_exhaustion_does_not_evict_an_active_entry() {
728 let store = MemoryStore::with_clock(
729 MemoryStoreConfig::new(1)
730 .unwrap()
731 .with_shard_count(1)
732 .unwrap(),
733 ManualClock::default(),
734 );
735 let policy = policy("auth.login", "client", 10, Duration::from_secs(60));
736
737 assert!(
738 store
739 .check(&Check::new(&policy, subject(1)))
740 .unwrap()
741 .is_allowed()
742 );
743 let denied = store.check(&Check::new(&policy, subject(2))).unwrap();
744 assert!(!denied.is_allowed());
745 assert_eq!(denied.retry_after(), Some(Duration::from_secs(60)));
746 assert_eq!(store.stats().unwrap().entries(), 1);
747 }
748
749 #[test]
750 fn default_configuration_can_use_its_entire_capacity() {
751 let store =
752 MemoryStore::with_clock(MemoryStoreConfig::new(64).unwrap(), ManualClock::default());
753 let policy = policy("auth.login", "client", 10, Duration::from_secs(60));
754
755 for byte in 0..64 {
756 assert!(
757 store
758 .check(&Check::new(&policy, subject(byte)))
759 .unwrap()
760 .is_allowed()
761 );
762 }
763
764 let denied = store.check(&Check::new(&policy, subject(64))).unwrap();
765 assert!(denied.is_denied());
766 assert_eq!(store.stats().unwrap().entries(), 64);
767 }
768
769 #[test]
770 fn expiry_cleanup_is_bounded_and_capacity_remains_hard_bounded() {
771 let clock = ManualClock::default();
772 let config = MemoryStoreConfig::new(3)
773 .unwrap()
774 .with_shard_count(1)
775 .unwrap()
776 .with_max_expired_removals_per_check(1)
777 .unwrap();
778 let store = MemoryStore::with_clock(config, clock.clone());
779 let policy = policy("auth.login", "client", 10, Duration::from_secs(1));
780
781 for byte in 1..=3 {
782 assert!(
783 store
784 .check(&Check::new(&policy, subject(byte)))
785 .unwrap()
786 .is_allowed()
787 );
788 }
789 clock.advance(Duration::from_secs(1));
790
791 assert!(
792 store
793 .check(&Check::new(&policy, subject(4)))
794 .unwrap()
795 .is_allowed()
796 );
797 assert_eq!(store.stats().unwrap().entries(), 3);
798
799 assert!(
800 store
801 .check(&Check::new(&policy, subject(5)))
802 .unwrap()
803 .is_allowed()
804 );
805 assert_eq!(store.stats().unwrap().entries(), 3);
806 }
807
808 #[test]
809 fn an_atomic_batch_receives_the_cleanup_budget_for_each_check() {
810 let clock = ManualClock::default();
811 let config = MemoryStoreConfig::new(3)
812 .unwrap()
813 .with_shard_count(1)
814 .unwrap()
815 .with_max_expired_removals_per_check(1)
816 .unwrap();
817 let store = MemoryStore::with_clock(config, clock.clone());
818 let policy = policy("auth.login", "client", 10, Duration::from_secs(1));
819
820 for byte in 1..=3 {
821 assert!(
822 store
823 .check(&Check::new(&policy, subject(byte)))
824 .unwrap()
825 .is_allowed()
826 );
827 }
828 clock.advance(Duration::from_secs(1));
829
830 let checks = [4, 5, 6].map(|byte| Check::new(&policy, subject(byte)));
831 let result = store.check_all(&checks).unwrap();
832 assert!(matches!(result, BatchDecision::Allowed(ref decisions) if decisions.len() == 3));
833 assert_eq!(store.stats().unwrap().entries(), 3);
834 }
835
836 #[test]
837 fn auxiliary_expiry_index_remains_bounded_across_many_windows() {
838 let clock = ManualClock::default();
839 let store = MemoryStore::with_clock(
840 MemoryStoreConfig::new(1)
841 .unwrap()
842 .with_shard_count(1)
843 .unwrap(),
844 clock.clone(),
845 );
846 let policy = policy("auth.login", "client", 1, Duration::from_millis(1));
847 let check = Check::new(&policy, subject(1));
848
849 for _ in 0..1_000 {
850 assert!(store.check(&check).unwrap().is_allowed());
851 clock.advance(Duration::from_millis(1));
852 }
853
854 let shard = store.shards[0].lock().unwrap();
855 assert_eq!(shard.entries.len(), 1);
856 assert_eq!(shard.expirations.len(), 1);
857 }
858
859 #[test]
860 fn targeted_expired_refresh_keeps_indexes_aligned_for_single_and_batch() {
861 for use_batch in [false, true] {
862 let clock = ManualClock::default();
863 let store = MemoryStore::with_clock(
864 MemoryStoreConfig::new(2)
865 .unwrap()
866 .with_shard_count(1)
867 .unwrap()
868 .with_max_expired_removals_per_check(1)
869 .unwrap(),
870 clock.clone(),
871 );
872 let policy = policy("auth.login", "client", 10, Duration::from_millis(2));
873 let earlier = Check::new(&policy, subject(1));
874 let target = Check::new(&policy, subject(2));
875
876 assert!(store.check(&earlier).unwrap().is_allowed());
877 clock.advance(Duration::from_millis(1));
878 assert!(store.check(&target).unwrap().is_allowed());
879 clock.advance(Duration::from_millis(2));
880
881 let decision = if use_batch {
882 store
883 .check_all(std::slice::from_ref(&target))
884 .unwrap()
885 .try_into_single_decision()
886 .expect("a one-element batch returns one decision")
887 } else {
888 store.check(&target).unwrap()
889 };
890 assert_eq!(decision, Decision::allowed(10, 9, Duration::from_millis(2)));
891
892 let key = target.counter_key();
893 let shard = store.shards[0].lock().unwrap();
894 assert_eq!(shard.entries.len(), 1);
895 assert_eq!(shard.expirations.len(), 1);
896 assert_eq!(
897 shard.entries.get(&key),
898 Some(&Entry {
899 used: 1,
900 expires_at_millis: 5,
901 })
902 );
903 assert!(shard.expirations.contains(&Expiration {
904 expires_at_millis: 5,
905 key,
906 }));
907 }
908 }
909
910 #[test]
911 fn a_denied_batch_does_not_consume_other_checks() {
912 let store = MemoryStore::with_clock(
913 MemoryStoreConfig::new(8)
914 .unwrap()
915 .with_shard_count(1)
916 .unwrap(),
917 ManualClock::default(),
918 );
919 let exhausted = policy("auth.login", "client", 1, Duration::from_secs(60));
920 let untouched = policy("auth.login", "identity", 1, Duration::from_secs(60));
921 let exhausted_check = Check::new(&exhausted, subject(1));
922 let untouched_check = Check::new(&untouched, subject(2));
923
924 assert!(store.check(&exhausted_check).unwrap().is_allowed());
925 let result = store
926 .check_all(&[exhausted_check, untouched_check])
927 .unwrap();
928 assert!(matches!(result, BatchDecision::Denied { index: 0, .. }));
929
930 assert!(
931 store
932 .check(&Check::new(&untouched, subject(2)))
933 .unwrap()
934 .is_allowed()
935 );
936 }
937
938 #[test]
939 fn duplicate_keys_are_rejected_before_consumption() {
940 let store =
941 MemoryStore::with_clock(MemoryStoreConfig::new(8).unwrap(), ManualClock::default());
942 let alpha = policy("auth.alpha", "client", 2, Duration::from_secs(60));
943 let beta = policy("auth.beta", "client", 2, Duration::from_secs(60));
944 let checks = [
945 Check::new(&beta, subject(1)),
946 Check::new(&beta, subject(1)),
947 Check::new(&alpha, subject(2)),
948 Check::new(&alpha, subject(2)),
949 ];
950
951 assert_eq!(
952 store.check_all(&checks),
953 Err(MemoryStoreError::InvalidBatch(BatchError::DuplicateKey {
954 first_index: 0,
955 duplicate_index: 1,
956 }))
957 );
958 assert_eq!(store.stats().unwrap().entries(), 0);
959 }
960
961 #[test]
962 fn concurrent_checks_never_over_admit() {
963 let store = Arc::new(MemoryStore::with_clock(
964 MemoryStoreConfig::new(8).unwrap(),
965 ManualClock::default(),
966 ));
967 let policy = Arc::new(policy("auth.login", "client", 25, Duration::from_secs(60)));
968
969 let allowed = (0..100)
970 .map(|_| {
971 let store = Arc::clone(&store);
972 let policy = Arc::clone(&policy);
973 thread::spawn(move || {
974 store
975 .check(&Check::new(&policy, subject(1)))
976 .unwrap()
977 .is_allowed()
978 })
979 })
980 .map(|thread| usize::from(thread.join().unwrap()))
981 .sum::<usize>();
982
983 assert_eq!(allowed, 25);
984 }
985
986 #[test]
987 fn a_poisoned_default_shard_remains_fail_closed() {
988 let clock = PanicOnceClock::default();
989 let store = MemoryStore::with_clock(
990 MemoryStoreConfig::new(1)
991 .unwrap()
992 .with_shard_count(1)
993 .unwrap(),
994 clock.clone(),
995 );
996 let policy = policy("auth.login", "client", 1, Duration::from_secs(60));
997 let exhausted = Check::new(&policy, subject(1));
998 let new_key = Check::new(&policy, subject(2));
999
1000 assert!(store.check(&exhausted).unwrap().is_allowed());
1001 clock.panic_once();
1002 let panic_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
1003 let _ = store.check(&new_key);
1004 }));
1005 assert!(panic_result.is_err());
1006
1007 let poisoned = Err(MemoryStoreError::PoisonedShard { shard_index: 0 });
1008 assert_eq!(store.check(&exhausted), poisoned);
1009 assert_eq!(store.check(&new_key), poisoned);
1010 assert_eq!(store.check(&exhausted), poisoned);
1011 assert_eq!(
1012 store.stats(),
1013 Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1014 );
1015 assert_eq!(
1016 store.clear(),
1017 Err(MemoryStoreError::PoisonedShard { shard_index: 0 })
1018 );
1019 }
1020}