Skip to main content

runlimit_memory/
store.rs

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
169/// A sharded, hard-bounded, process-local fixed-window store.
170///
171/// The store never evicts an active key to admit a new one. Every check touches
172/// only the shards required by that check and performs a bounded amount of
173/// expiry cleanup. An atomic batch locks its shards in deterministic order.
174///
175/// If application code panics while a shard is locked, that shard remains
176/// poisoned and every later operation touching it fails closed with
177/// [`MemoryStoreError::PoisonedShard`]. Replace the store explicitly rather
178/// than automatically resetting quota for counters whose consistency is
179/// unknown.
180pub 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    /// Creates a store using the system monotonic clock.
189    pub fn new(config: MemoryStoreConfig) -> Self {
190        Self::with_clock(config, SystemClock::new())
191    }
192}
193
194impl<C: Clock> MemoryStore<C> {
195    /// Creates a store using a caller-supplied monotonic clock.
196    ///
197    /// Supplying a clock is primarily useful for deterministic tests.
198    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    /// Evaluates and, when allowed, consumes one check.
213    ///
214    /// # Errors
215    ///
216    /// Returns an error without allowing the request when the target shard is
217    /// poisoned.
218    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    /// Evaluates a batch atomically.
241    ///
242    /// If any check is denied, none of the checks consumes quota. Returned
243    /// allowed decisions preserve input order.
244    ///
245    /// # Errors
246    ///
247    /// Returns an error before quota consumption when the batch exceeds its
248    /// configured bound, contains a duplicate key, or a touched shard is
249    /// poisoned.
250    ///
251    #[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    /// Returns current storage usage.
336    ///
337    /// # Errors
338    ///
339    /// Returns an error if a shard is poisoned.
340    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    /// Removes every stored counter.
354    ///
355    /// # Errors
356    ///
357    /// Returns an error if a shard is poisoned.
358    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/// Current bounded-store usage.
399#[derive(Clone, Copy, Debug, Eq, PartialEq)]
400pub struct MemoryStoreStats {
401    entries: usize,
402    capacity: usize,
403    shard_count: usize,
404}
405
406impl MemoryStoreStats {
407    /// Returns the number of stored counters.
408    pub const fn entries(self) -> usize {
409        self.entries
410    }
411
412    /// Returns the hard maximum number of stored counters.
413    pub const fn capacity(self) -> usize {
414        self.capacity
415    }
416
417    /// Returns the number of independently locked shards.
418    pub const fn shard_count(self) -> usize {
419        self.shard_count
420    }
421}
422
423/// A fail-closed in-memory store error.
424#[derive(Clone, Debug, Error, Eq, PartialEq)]
425pub enum MemoryStoreError {
426    /// The atomic batch violated a backend-independent structural requirement.
427    #[error(transparent)]
428    InvalidBatch(#[from] BatchError),
429    /// A shard mutex was poisoned and remains unavailable.
430    #[error("memory-store shard {shard_index} is poisoned and unavailable")]
431    PoisonedShard {
432        /// Poisoned shard index.
433        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}