1use std::collections::hash_map::RandomState;
4use std::hash::BuildHasher;
5use std::net::IpAddr;
6use std::num::{NonZeroU32, NonZeroUsize};
7use std::sync::atomic::{AtomicU64, Ordering};
8use std::sync::{Arc, Mutex};
9use std::time::{Duration as MonotonicDuration, Instant};
10
11use dashmap::DashMap;
12use time::Duration;
13
14const DEFAULT_MAX_TRACKED_KEYS: usize = 10_000;
15const PRUNE_EVERY_CHECKS: u64 = 256;
16
17#[derive(Clone, Debug)]
18struct TokenBucket {
19 token_units: u128,
20 capacity: u128,
21 refill_interval_nanos: u128,
22 last_refill_at: MonotonicDuration,
23 last_seen_at: MonotonicDuration,
24 last_seen_order: u64,
25}
26
27impl TokenBucket {
28 fn new(
29 capacity: NonZeroU32,
30 refill_interval: MonotonicDuration,
31 now: MonotonicDuration,
32 access_order: u64,
33 ) -> Self {
34 let capacity = u128::from(capacity.get());
35 let refill_interval_nanos = refill_interval.as_nanos();
36 Self {
37 token_units: capacity.saturating_mul(refill_interval_nanos),
38 capacity,
39 refill_interval_nanos,
40 last_refill_at: now,
41 last_seen_at: now,
42 last_seen_order: access_order,
43 }
44 }
45
46 fn refill(&mut self, now: MonotonicDuration) {
47 if now <= self.last_refill_at {
48 return;
49 }
50 let elapsed_nanos = now.saturating_sub(self.last_refill_at).as_nanos();
51 let replenished = elapsed_nanos.saturating_mul(self.capacity);
52 let maximum = self.capacity.saturating_mul(self.refill_interval_nanos);
53 self.token_units = self.token_units.saturating_add(replenished).min(maximum);
54 self.last_refill_at = now;
55 }
56
57 fn take(&mut self, now: MonotonicDuration, access_order: u64) -> (bool, u32, u64) {
58 self.last_seen_at = now;
59 self.last_seen_order = access_order;
60 self.refill(now);
61 if self.token_units >= self.refill_interval_nanos {
62 self.token_units -= self.refill_interval_nanos;
63 let remaining = self.token_units / self.refill_interval_nanos;
64 return (true, u32::try_from(remaining).unwrap_or(u32::MAX), 0);
65 }
66
67 let missing_units = self.refill_interval_nanos - self.token_units;
68 let retry_after_nanos = missing_units.div_ceil(self.capacity);
69 let retry_after_secs =
70 u64::try_from(retry_after_nanos.div_ceil(1_000_000_000).max(1)).unwrap_or(u64::MAX);
71 (false, 0, retry_after_secs)
72 }
73}
74
75#[derive(Clone, Copy, Debug, thiserror::Error, PartialEq, Eq)]
77#[error("rate-limit refill interval must be positive")]
78pub struct RateLimiterConfigError;
79
80#[derive(Clone, Debug, PartialEq, Eq)]
82pub struct RateLimitOutcome {
83 pub allowed: bool,
85 pub remaining: u32,
87 pub capacity: u32,
89 pub retry_after_secs: u64,
91}
92
93#[derive(Clone, Debug)]
100pub struct RateLimiter {
101 inner: Arc<RateLimiterInner>,
102}
103
104#[derive(Debug)]
105struct RateLimiterInner {
106 buckets: DashMap<u64, TokenBucket>,
107 capacity: NonZeroU32,
108 refill_interval: MonotonicDuration,
109 max_tracked_keys: usize,
110 checks: AtomicU64,
111 access_sequence: AtomicU64,
112 started_at: Instant,
113 key_hasher: RandomState,
114 admission: Mutex<()>,
115}
116
117impl RateLimiter {
118 pub fn new(
121 capacity: NonZeroU32,
122 refill_interval: Duration,
123 ) -> Result<Self, RateLimiterConfigError> {
124 Self::with_max_tracked_keys(
125 capacity,
126 refill_interval,
127 NonZeroUsize::new(DEFAULT_MAX_TRACKED_KEYS).expect("constant is non-zero"),
128 )
129 }
130
131 pub fn with_max_tracked_keys(
133 capacity: NonZeroU32,
134 refill_interval: Duration,
135 max_tracked_keys: NonZeroUsize,
136 ) -> Result<Self, RateLimiterConfigError> {
137 let refill_interval = monotonic_duration(refill_interval)?;
138 Ok(Self {
139 inner: Arc::new(RateLimiterInner {
140 buckets: DashMap::new(),
141 capacity,
142 refill_interval,
143 max_tracked_keys: max_tracked_keys.get(),
144 checks: AtomicU64::new(0),
145 access_sequence: AtomicU64::new(0),
146 started_at: Instant::now(),
147 key_hasher: RandomState::new(),
148 admission: Mutex::new(()),
149 }),
150 })
151 }
152
153 #[must_use]
155 pub fn check(&self, key: impl AsRef<str>) -> RateLimitOutcome {
156 self.check_at_elapsed(key.as_ref(), self.inner.started_at.elapsed())
157 }
158
159 pub fn reset(&self, key: impl AsRef<str>) {
161 let key = self.inner.key_hasher.hash_one(key.as_ref().as_bytes());
162 self.inner.buckets.remove(&key);
163 }
164
165 fn check_at_elapsed(&self, key: &str, now: MonotonicDuration) -> RateLimitOutcome {
166 self.prune_stale_buckets(now);
167 let access_order = self.inner.access_sequence.fetch_add(1, Ordering::Relaxed);
168
169 let key = self.inner.key_hasher.hash_one(key.as_bytes());
170 if let Some(mut entry) = self.inner.buckets.get_mut(&key) {
171 return outcome_from_bucket(entry.value_mut(), self.inner.capacity, now, access_order);
172 }
173
174 let _admission = self
175 .inner
176 .admission
177 .lock()
178 .unwrap_or_else(std::sync::PoisonError::into_inner);
179 if let Some(mut entry) = self.inner.buckets.get_mut(&key) {
180 return outcome_from_bucket(entry.value_mut(), self.inner.capacity, now, access_order);
181 }
182 self.make_room_for_key(now);
183 self.inner.buckets.insert(
184 key,
185 TokenBucket::new(
186 self.inner.capacity,
187 self.inner.refill_interval,
188 now,
189 access_order,
190 ),
191 );
192 let mut entry = self
193 .inner
194 .buckets
195 .get_mut(&key)
196 .expect("the admission lock inserts a missing bucket");
197 outcome_from_bucket(entry.value_mut(), self.inner.capacity, now, access_order)
198 }
199
200 fn prune_stale_buckets(&self, now: MonotonicDuration) {
201 let check = self.inner.checks.fetch_add(1, Ordering::Relaxed) + 1;
202 if !check.is_multiple_of(PRUNE_EVERY_CHECKS) {
203 return;
204 }
205 let _admission = self
206 .inner
207 .admission
208 .lock()
209 .unwrap_or_else(std::sync::PoisonError::into_inner);
210 let stale_before = now.saturating_sub(self.inner.refill_interval.saturating_mul(2));
211 self.inner
212 .buckets
213 .retain(|_, bucket| bucket.last_seen_at >= stale_before);
214 }
215
216 fn make_room_for_key(&self, now: MonotonicDuration) {
217 if self.inner.buckets.len() < self.inner.max_tracked_keys {
218 return;
219 }
220
221 let stale_before = now.saturating_sub(self.inner.refill_interval.saturating_mul(2));
222 self.inner
223 .buckets
224 .retain(|_, bucket| bucket.last_seen_at >= stale_before);
225 if self.inner.buckets.len() < self.inner.max_tracked_keys {
226 return;
227 }
228
229 let oldest = self
230 .inner
231 .buckets
232 .iter()
233 .min_by_key(|entry| (entry.value().last_seen_at, entry.value().last_seen_order))
234 .map(|entry| *entry.key());
235 if let Some(oldest) = oldest {
236 self.inner.buckets.remove(&oldest);
237 }
238 }
239}
240
241fn outcome_from_bucket(
242 bucket: &mut TokenBucket,
243 capacity: NonZeroU32,
244 now: MonotonicDuration,
245 access_order: u64,
246) -> RateLimitOutcome {
247 let (allowed, remaining, retry_after_secs) = bucket.take(now, access_order);
248 RateLimitOutcome {
249 allowed,
250 remaining,
251 capacity: capacity.get(),
252 retry_after_secs,
253 }
254}
255
256fn monotonic_duration(value: Duration) -> Result<MonotonicDuration, RateLimiterConfigError> {
257 if !value.is_positive() {
258 return Err(RateLimiterConfigError);
259 }
260 let nanoseconds = value.whole_nanoseconds();
261 let nanoseconds = u64::try_from(nanoseconds).map_err(|_| RateLimiterConfigError)?;
262 Ok(MonotonicDuration::from_nanos(nanoseconds))
263}
264
265#[derive(Clone, Copy, Debug, PartialEq, Eq)]
267pub enum AuthRateLimitScope {
268 LoginIp,
270 LoginAccount,
272 TwoFactorIp,
274 TwoFactorAccount,
276 RegistrationIp,
278 PasswordResetIp,
280}
281
282#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
284#[error("authentication rate limit exceeded for {scope:?}")]
285pub struct AuthRateLimitRejection {
286 pub scope: AuthRateLimitScope,
288 pub outcome: RateLimitOutcome,
290}
291
292#[derive(Clone, Copy, Debug, PartialEq, Eq)]
294pub struct AuthRateLimitPolicy {
295 pub login_ip_per_minute: NonZeroU32,
297 pub login_account_per_minute: NonZeroU32,
299 pub two_factor_ip_per_minute: NonZeroU32,
301 pub two_factor_account_per_minute: NonZeroU32,
303 pub registration_ip_per_minute: NonZeroU32,
305}
306
307impl Default for AuthRateLimitPolicy {
308 fn default() -> Self {
309 Self {
310 login_ip_per_minute: NonZeroU32::new(10).expect("constant is non-zero"),
311 login_account_per_minute: NonZeroU32::new(5).expect("constant is non-zero"),
312 two_factor_ip_per_minute: NonZeroU32::new(10).expect("constant is non-zero"),
313 two_factor_account_per_minute: NonZeroU32::new(5).expect("constant is non-zero"),
314 registration_ip_per_minute: NonZeroU32::new(5).expect("constant is non-zero"),
315 }
316 }
317}
318
319#[derive(Clone, Debug)]
321pub struct SecurityState {
322 pub captcha_issuance: RateLimiter,
324 pub captcha_validation_ip: RateLimiter,
326 pub captcha_validation_account: RateLimiter,
328 login_ip: RateLimiter,
329 login_account: RateLimiter,
330 two_factor_ip: RateLimiter,
331 two_factor_account: RateLimiter,
332 registration_ip: RateLimiter,
333 password_reset_ip: RateLimiter,
334}
335
336impl SecurityState {
337 #[must_use]
339 pub fn new(captcha_budget_per_minute: NonZeroU32) -> Self {
340 Self::with_auth_policy(captcha_budget_per_minute, AuthRateLimitPolicy::default())
341 }
342
343 #[must_use]
345 pub fn with_auth_policy(
346 captcha_budget_per_minute: NonZeroU32,
347 auth_policy: AuthRateLimitPolicy,
348 ) -> Self {
349 let per_minute = Duration::minutes(1);
350 Self {
351 captcha_issuance: RateLimiter::new(captcha_budget_per_minute, per_minute)
352 .expect("one minute is a valid refill interval"),
353 captcha_validation_ip: RateLimiter::new(captcha_budget_per_minute, per_minute)
354 .expect("one minute is a valid refill interval"),
355 captcha_validation_account: RateLimiter::new(captcha_budget_per_minute, per_minute)
356 .expect("one minute is a valid refill interval"),
357 login_ip: RateLimiter::new(auth_policy.login_ip_per_minute, per_minute)
358 .expect("one minute is a valid refill interval"),
359 login_account: RateLimiter::new(auth_policy.login_account_per_minute, per_minute)
360 .expect("one minute is a valid refill interval"),
361 two_factor_ip: RateLimiter::new(auth_policy.two_factor_ip_per_minute, per_minute)
362 .expect("one minute is a valid refill interval"),
363 two_factor_account: RateLimiter::new(
364 auth_policy.two_factor_account_per_minute,
365 per_minute,
366 )
367 .expect("one minute is a valid refill interval"),
368 registration_ip: RateLimiter::new(auth_policy.registration_ip_per_minute, per_minute)
369 .expect("one minute is a valid refill interval"),
370 password_reset_ip: RateLimiter::new(
371 NonZeroU32::new(5).expect("constant is non-zero"),
372 per_minute,
373 )
374 .expect("one minute is a valid refill interval"),
375 }
376 }
377
378 #[must_use]
380 pub fn client_key(&self, peer_ip: IpAddr) -> String {
381 peer_ip.to_string()
382 }
383
384 pub fn check_login(
386 &self,
387 client_key: &str,
388 account_identifier: &str,
389 ) -> Result<(), AuthRateLimitRejection> {
390 check_auth_limiter(
391 &self.login_ip,
392 format!("login:ip:{client_key}"),
393 AuthRateLimitScope::LoginIp,
394 )?;
395 check_auth_limiter(
396 &self.login_account,
397 format!("login:account:{}", account_identifier.trim().to_lowercase()),
398 AuthRateLimitScope::LoginAccount,
399 )
400 }
401
402 pub fn reset_login(&self, client_key: &str, account_identifier: &str) {
407 self.login_ip.reset(format!("login:ip:{client_key}"));
408 self.login_account.reset(format!(
409 "login:account:{}",
410 account_identifier.trim().to_lowercase()
411 ));
412 }
413
414 pub fn check_two_factor(&self, client_key: &str) -> Result<(), AuthRateLimitRejection> {
416 check_auth_limiter(
417 &self.two_factor_ip,
418 format!("two-factor:ip:{client_key}"),
419 AuthRateLimitScope::TwoFactorIp,
420 )
421 }
422
423 pub fn check_two_factor_account(&self, account_id: &str) -> Result<(), AuthRateLimitRejection> {
426 check_auth_limiter(
427 &self.two_factor_account,
428 account_id,
429 AuthRateLimitScope::TwoFactorAccount,
430 )
431 }
432
433 pub fn check_registration(&self, client_key: &str) -> Result<(), AuthRateLimitRejection> {
435 check_auth_limiter(
436 &self.registration_ip,
437 format!("registration:ip:{client_key}"),
438 AuthRateLimitScope::RegistrationIp,
439 )
440 }
441
442 pub fn check_password_reset(&self, client_key: &str) -> Result<(), AuthRateLimitRejection> {
444 check_auth_limiter(
445 &self.password_reset_ip,
446 format!("password-reset:ip:{client_key}"),
447 AuthRateLimitScope::PasswordResetIp,
448 )
449 }
450}
451
452fn check_auth_limiter(
453 limiter: &RateLimiter,
454 key: impl AsRef<str>,
455 scope: AuthRateLimitScope,
456) -> Result<(), AuthRateLimitRejection> {
457 let outcome = limiter.check(key);
458 if outcome.allowed {
459 Ok(())
460 } else {
461 Err(AuthRateLimitRejection { scope, outcome })
462 }
463}
464
465#[cfg(test)]
466mod tests {
467 use std::net::{IpAddr, Ipv4Addr};
468 use std::num::{NonZeroU32, NonZeroUsize};
469
470 use time::Duration;
471
472 use super::{AuthRateLimitPolicy, RateLimiter, SecurityState};
473
474 #[test]
475 fn second_factor_account_budget_survives_client_changes_and_password_success() {
476 let security = SecurityState::with_auth_policy(
477 100.try_into().unwrap(),
478 AuthRateLimitPolicy {
479 two_factor_account_per_minute: 2.try_into().unwrap(),
480 ..AuthRateLimitPolicy::default()
481 },
482 );
483 assert!(security.check_two_factor("192.0.2.1").is_ok());
484 assert!(security.check_two_factor_account("account-a").is_ok());
485 security.reset_login("192.0.2.1", "account-a");
486 assert!(security.clone().check_two_factor("192.0.2.2").is_ok());
487 assert!(
488 security
489 .clone()
490 .check_two_factor_account("account-a")
491 .is_ok()
492 );
493 let rejected = security
494 .check_two_factor_account("account-a")
495 .expect_err("account budget exhausted");
496 assert_eq!(rejected.scope, super::AuthRateLimitScope::TwoFactorAccount);
497 assert!(security.check_two_factor_account("account-b").is_ok());
498 }
499
500 #[test]
501 fn cloned_rate_limiter_shares_buckets() {
502 let limiter = RateLimiter::new(NonZeroU32::new(1).unwrap(), Duration::minutes(1))
503 .expect("valid limiter");
504 let cloned = limiter.clone();
505 assert!(limiter.check("same").allowed);
506 assert!(!cloned.check("same").allowed);
507 }
508
509 #[test]
510 fn rejects_non_positive_refill_intervals() {
511 assert!(RateLimiter::new(NonZeroU32::new(1).unwrap(), Duration::ZERO).is_err());
512 }
513
514 #[test]
515 fn bounded_limiter_evicts_oldest_key_without_a_shared_overflow_bucket() {
516 let limiter = RateLimiter::with_max_tracked_keys(
517 NonZeroU32::new(1).unwrap(),
518 Duration::minutes(1),
519 NonZeroUsize::new(2).unwrap(),
520 )
521 .expect("valid limiter");
522 let start = std::time::Duration::ZERO;
523 assert!(limiter.check_at_elapsed("one", start).allowed);
524 assert!(limiter.check_at_elapsed("two", start).allowed);
525 assert!(limiter.check_at_elapsed("three", start).allowed);
526 assert!(limiter.check_at_elapsed("one", start).allowed);
527 assert!(limiter.inner.buckets.len() <= 2);
528 }
529
530 #[test]
531 fn auth_budgets_are_independent() {
532 let state = SecurityState::new(NonZeroU32::new(1).unwrap());
533 assert!(state.check_login("client", "user@example.test").is_ok());
534 assert!(state.check_registration("client").is_ok());
535 assert!(state.check_two_factor("client").is_ok());
536 assert!(state.check_password_reset("client").is_ok());
537 }
538
539 #[test]
540 fn password_reset_budget_is_bounded_per_client_address() {
541 let state = SecurityState::new(NonZeroU32::new(100).unwrap());
542
543 for _ in 0..5 {
544 assert!(state.check_password_reset("client-a").is_ok());
545 }
546 let rejection = state
547 .check_password_reset("client-a")
548 .expect_err("sixth reset attempt in one minute must be rejected");
549 assert_eq!(rejection.scope, super::AuthRateLimitScope::PasswordResetIp);
550 assert!(state.check_password_reset("client-b").is_ok());
551 }
552
553 #[test]
554 fn accepted_login_can_reset_consumed_client_and_account_budgets() {
555 let one = NonZeroU32::new(1).unwrap();
556 let state = SecurityState::with_auth_policy(
557 one,
558 AuthRateLimitPolicy {
559 login_ip_per_minute: one,
560 login_account_per_minute: one,
561 two_factor_ip_per_minute: one,
562 two_factor_account_per_minute: one,
563 registration_ip_per_minute: one,
564 },
565 );
566
567 assert!(state.check_login("client", "user@example.test").is_ok());
568 assert!(state.check_login("client", "user@example.test").is_err());
569
570 state.reset_login("client", " USER@EXAMPLE.TEST ");
571
572 assert!(state.check_login("client", "user@example.test").is_ok());
573 }
574
575 #[test]
576 fn client_keys_use_the_tcp_peer_address() {
577 let state = SecurityState::new(NonZeroU32::new(1).unwrap());
578 let peer_ip = IpAddr::V4(Ipv4Addr::new(192, 0, 2, 40));
579 assert_eq!(state.client_key(peer_ip), "192.0.2.40");
580 }
581}