use std::collections::hash_map::RandomState;
use std::hash::BuildHasher;
use std::net::IpAddr;
use std::num::{NonZeroU32, NonZeroUsize};
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex};
use std::time::{Duration as MonotonicDuration, Instant};
use dashmap::DashMap;
use time::Duration;
const DEFAULT_MAX_TRACKED_KEYS: usize = 10_000;
const PRUNE_EVERY_CHECKS: u64 = 256;
#[derive(Clone, Debug)]
struct TokenBucket {
token_units: u128,
capacity: u128,
refill_interval_nanos: u128,
last_refill_at: MonotonicDuration,
last_seen_at: MonotonicDuration,
last_seen_order: u64,
}
impl TokenBucket {
fn new(
capacity: NonZeroU32,
refill_interval: MonotonicDuration,
now: MonotonicDuration,
access_order: u64,
) -> Self {
let capacity = u128::from(capacity.get());
let refill_interval_nanos = refill_interval.as_nanos();
Self {
token_units: capacity.saturating_mul(refill_interval_nanos),
capacity,
refill_interval_nanos,
last_refill_at: now,
last_seen_at: now,
last_seen_order: access_order,
}
}
fn refill(&mut self, now: MonotonicDuration) {
if now <= self.last_refill_at {
return;
}
let elapsed_nanos = now.saturating_sub(self.last_refill_at).as_nanos();
let replenished = elapsed_nanos.saturating_mul(self.capacity);
let maximum = self.capacity.saturating_mul(self.refill_interval_nanos);
self.token_units = self.token_units.saturating_add(replenished).min(maximum);
self.last_refill_at = now;
}
fn take(&mut self, now: MonotonicDuration, access_order: u64) -> (bool, u32, u64) {
self.last_seen_at = now;
self.last_seen_order = access_order;
self.refill(now);
if self.token_units >= self.refill_interval_nanos {
self.token_units -= self.refill_interval_nanos;
let remaining = self.token_units / self.refill_interval_nanos;
return (true, u32::try_from(remaining).unwrap_or(u32::MAX), 0);
}
let missing_units = self.refill_interval_nanos - self.token_units;
let retry_after_nanos = missing_units.div_ceil(self.capacity);
let retry_after_secs =
u64::try_from(retry_after_nanos.div_ceil(1_000_000_000).max(1)).unwrap_or(u64::MAX);
(false, 0, retry_after_secs)
}
}
#[derive(Clone, Copy, Debug, thiserror::Error, PartialEq, Eq)]
#[error("rate-limit refill interval must be positive")]
pub struct RateLimiterConfigError;
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct RateLimitOutcome {
pub allowed: bool,
pub remaining: u32,
pub capacity: u32,
pub retry_after_secs: u64,
}
#[derive(Clone, Debug)]
pub struct RateLimiter {
inner: Arc<RateLimiterInner>,
}
#[derive(Debug)]
struct RateLimiterInner {
buckets: DashMap<u64, TokenBucket>,
capacity: NonZeroU32,
refill_interval: MonotonicDuration,
max_tracked_keys: usize,
checks: AtomicU64,
access_sequence: AtomicU64,
started_at: Instant,
key_hasher: RandomState,
admission: Mutex<()>,
}
impl RateLimiter {
pub fn new(
capacity: NonZeroU32,
refill_interval: Duration,
) -> Result<Self, RateLimiterConfigError> {
Self::with_max_tracked_keys(
capacity,
refill_interval,
NonZeroUsize::new(DEFAULT_MAX_TRACKED_KEYS).expect("constant is non-zero"),
)
}
pub fn with_max_tracked_keys(
capacity: NonZeroU32,
refill_interval: Duration,
max_tracked_keys: NonZeroUsize,
) -> Result<Self, RateLimiterConfigError> {
let refill_interval = monotonic_duration(refill_interval)?;
Ok(Self {
inner: Arc::new(RateLimiterInner {
buckets: DashMap::new(),
capacity,
refill_interval,
max_tracked_keys: max_tracked_keys.get(),
checks: AtomicU64::new(0),
access_sequence: AtomicU64::new(0),
started_at: Instant::now(),
key_hasher: RandomState::new(),
admission: Mutex::new(()),
}),
})
}
#[must_use]
pub fn check(&self, key: impl AsRef<str>) -> RateLimitOutcome {
self.check_at_elapsed(key.as_ref(), self.inner.started_at.elapsed())
}
pub fn reset(&self, key: impl AsRef<str>) {
let key = self.inner.key_hasher.hash_one(key.as_ref().as_bytes());
self.inner.buckets.remove(&key);
}
fn check_at_elapsed(&self, key: &str, now: MonotonicDuration) -> RateLimitOutcome {
self.prune_stale_buckets(now);
let access_order = self.inner.access_sequence.fetch_add(1, Ordering::Relaxed);
let key = self.inner.key_hasher.hash_one(key.as_bytes());
if let Some(mut entry) = self.inner.buckets.get_mut(&key) {
return outcome_from_bucket(entry.value_mut(), self.inner.capacity, now, access_order);
}
let _admission = self
.inner
.admission
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner);
if let Some(mut entry) = self.inner.buckets.get_mut(&key) {
return outcome_from_bucket(entry.value_mut(), self.inner.capacity, now, access_order);
}
self.make_room_for_key(now);
self.inner.buckets.insert(
key,
TokenBucket::new(
self.inner.capacity,
self.inner.refill_interval,
now,
access_order,
),
);
let mut entry = self
.inner
.buckets
.get_mut(&key)
.expect("the admission lock inserts a missing bucket");
outcome_from_bucket(entry.value_mut(), self.inner.capacity, now, access_order)
}
fn prune_stale_buckets(&self, now: MonotonicDuration) {
let check = self.inner.checks.fetch_add(1, Ordering::Relaxed) + 1;
if !check.is_multiple_of(PRUNE_EVERY_CHECKS) {
return;
}
let _admission = self
.inner
.admission
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner);
let stale_before = now.saturating_sub(self.inner.refill_interval.saturating_mul(2));
self.inner
.buckets
.retain(|_, bucket| bucket.last_seen_at >= stale_before);
}
fn make_room_for_key(&self, now: MonotonicDuration) {
if self.inner.buckets.len() < self.inner.max_tracked_keys {
return;
}
let stale_before = now.saturating_sub(self.inner.refill_interval.saturating_mul(2));
self.inner
.buckets
.retain(|_, bucket| bucket.last_seen_at >= stale_before);
if self.inner.buckets.len() < self.inner.max_tracked_keys {
return;
}
let oldest = self
.inner
.buckets
.iter()
.min_by_key(|entry| (entry.value().last_seen_at, entry.value().last_seen_order))
.map(|entry| *entry.key());
if let Some(oldest) = oldest {
self.inner.buckets.remove(&oldest);
}
}
}
fn outcome_from_bucket(
bucket: &mut TokenBucket,
capacity: NonZeroU32,
now: MonotonicDuration,
access_order: u64,
) -> RateLimitOutcome {
let (allowed, remaining, retry_after_secs) = bucket.take(now, access_order);
RateLimitOutcome {
allowed,
remaining,
capacity: capacity.get(),
retry_after_secs,
}
}
fn monotonic_duration(value: Duration) -> Result<MonotonicDuration, RateLimiterConfigError> {
if !value.is_positive() {
return Err(RateLimiterConfigError);
}
let nanoseconds = value.whole_nanoseconds();
let nanoseconds = u64::try_from(nanoseconds).map_err(|_| RateLimiterConfigError)?;
Ok(MonotonicDuration::from_nanos(nanoseconds))
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum AuthRateLimitScope {
LoginIp,
LoginAccount,
TwoFactorIp,
TwoFactorAccount,
RegistrationIp,
PasswordResetIp,
}
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
#[error("authentication rate limit exceeded for {scope:?}")]
pub struct AuthRateLimitRejection {
pub scope: AuthRateLimitScope,
pub outcome: RateLimitOutcome,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct AuthRateLimitPolicy {
pub login_ip_per_minute: NonZeroU32,
pub login_account_per_minute: NonZeroU32,
pub two_factor_ip_per_minute: NonZeroU32,
pub two_factor_account_per_minute: NonZeroU32,
pub registration_ip_per_minute: NonZeroU32,
}
impl Default for AuthRateLimitPolicy {
fn default() -> Self {
Self {
login_ip_per_minute: NonZeroU32::new(10).expect("constant is non-zero"),
login_account_per_minute: NonZeroU32::new(5).expect("constant is non-zero"),
two_factor_ip_per_minute: NonZeroU32::new(10).expect("constant is non-zero"),
two_factor_account_per_minute: NonZeroU32::new(5).expect("constant is non-zero"),
registration_ip_per_minute: NonZeroU32::new(5).expect("constant is non-zero"),
}
}
}
#[derive(Clone, Debug)]
pub struct SecurityState {
pub captcha_issuance: RateLimiter,
pub captcha_validation_ip: RateLimiter,
pub captcha_validation_account: RateLimiter,
login_ip: RateLimiter,
login_account: RateLimiter,
two_factor_ip: RateLimiter,
two_factor_account: RateLimiter,
registration_ip: RateLimiter,
password_reset_ip: RateLimiter,
}
impl SecurityState {
#[must_use]
pub fn new(captcha_budget_per_minute: NonZeroU32) -> Self {
Self::with_auth_policy(captcha_budget_per_minute, AuthRateLimitPolicy::default())
}
#[must_use]
pub fn with_auth_policy(
captcha_budget_per_minute: NonZeroU32,
auth_policy: AuthRateLimitPolicy,
) -> Self {
let per_minute = Duration::minutes(1);
Self {
captcha_issuance: RateLimiter::new(captcha_budget_per_minute, per_minute)
.expect("one minute is a valid refill interval"),
captcha_validation_ip: RateLimiter::new(captcha_budget_per_minute, per_minute)
.expect("one minute is a valid refill interval"),
captcha_validation_account: RateLimiter::new(captcha_budget_per_minute, per_minute)
.expect("one minute is a valid refill interval"),
login_ip: RateLimiter::new(auth_policy.login_ip_per_minute, per_minute)
.expect("one minute is a valid refill interval"),
login_account: RateLimiter::new(auth_policy.login_account_per_minute, per_minute)
.expect("one minute is a valid refill interval"),
two_factor_ip: RateLimiter::new(auth_policy.two_factor_ip_per_minute, per_minute)
.expect("one minute is a valid refill interval"),
two_factor_account: RateLimiter::new(
auth_policy.two_factor_account_per_minute,
per_minute,
)
.expect("one minute is a valid refill interval"),
registration_ip: RateLimiter::new(auth_policy.registration_ip_per_minute, per_minute)
.expect("one minute is a valid refill interval"),
password_reset_ip: RateLimiter::new(
NonZeroU32::new(5).expect("constant is non-zero"),
per_minute,
)
.expect("one minute is a valid refill interval"),
}
}
#[must_use]
pub fn client_key(&self, peer_ip: IpAddr) -> String {
peer_ip.to_string()
}
pub fn check_login(
&self,
client_key: &str,
account_identifier: &str,
) -> Result<(), AuthRateLimitRejection> {
check_auth_limiter(
&self.login_ip,
format!("login:ip:{client_key}"),
AuthRateLimitScope::LoginIp,
)?;
check_auth_limiter(
&self.login_account,
format!("login:account:{}", account_identifier.trim().to_lowercase()),
AuthRateLimitScope::LoginAccount,
)
}
pub fn reset_login(&self, client_key: &str, account_identifier: &str) {
self.login_ip.reset(format!("login:ip:{client_key}"));
self.login_account.reset(format!(
"login:account:{}",
account_identifier.trim().to_lowercase()
));
}
pub fn check_two_factor(&self, client_key: &str) -> Result<(), AuthRateLimitRejection> {
check_auth_limiter(
&self.two_factor_ip,
format!("two-factor:ip:{client_key}"),
AuthRateLimitScope::TwoFactorIp,
)
}
pub fn check_two_factor_account(&self, account_id: &str) -> Result<(), AuthRateLimitRejection> {
check_auth_limiter(
&self.two_factor_account,
account_id,
AuthRateLimitScope::TwoFactorAccount,
)
}
pub fn check_registration(&self, client_key: &str) -> Result<(), AuthRateLimitRejection> {
check_auth_limiter(
&self.registration_ip,
format!("registration:ip:{client_key}"),
AuthRateLimitScope::RegistrationIp,
)
}
pub fn check_password_reset(&self, client_key: &str) -> Result<(), AuthRateLimitRejection> {
check_auth_limiter(
&self.password_reset_ip,
format!("password-reset:ip:{client_key}"),
AuthRateLimitScope::PasswordResetIp,
)
}
}
fn check_auth_limiter(
limiter: &RateLimiter,
key: impl AsRef<str>,
scope: AuthRateLimitScope,
) -> Result<(), AuthRateLimitRejection> {
let outcome = limiter.check(key);
if outcome.allowed {
Ok(())
} else {
Err(AuthRateLimitRejection { scope, outcome })
}
}
#[cfg(test)]
mod tests {
use std::net::{IpAddr, Ipv4Addr};
use std::num::{NonZeroU32, NonZeroUsize};
use time::Duration;
use super::{AuthRateLimitPolicy, RateLimiter, SecurityState};
#[test]
fn second_factor_account_budget_survives_client_changes_and_password_success() {
let security = SecurityState::with_auth_policy(
100.try_into().unwrap(),
AuthRateLimitPolicy {
two_factor_account_per_minute: 2.try_into().unwrap(),
..AuthRateLimitPolicy::default()
},
);
assert!(security.check_two_factor("192.0.2.1").is_ok());
assert!(security.check_two_factor_account("account-a").is_ok());
security.reset_login("192.0.2.1", "account-a");
assert!(security.clone().check_two_factor("192.0.2.2").is_ok());
assert!(
security
.clone()
.check_two_factor_account("account-a")
.is_ok()
);
let rejected = security
.check_two_factor_account("account-a")
.expect_err("account budget exhausted");
assert_eq!(rejected.scope, super::AuthRateLimitScope::TwoFactorAccount);
assert!(security.check_two_factor_account("account-b").is_ok());
}
#[test]
fn cloned_rate_limiter_shares_buckets() {
let limiter = RateLimiter::new(NonZeroU32::new(1).unwrap(), Duration::minutes(1))
.expect("valid limiter");
let cloned = limiter.clone();
assert!(limiter.check("same").allowed);
assert!(!cloned.check("same").allowed);
}
#[test]
fn rejects_non_positive_refill_intervals() {
assert!(RateLimiter::new(NonZeroU32::new(1).unwrap(), Duration::ZERO).is_err());
}
#[test]
fn bounded_limiter_evicts_oldest_key_without_a_shared_overflow_bucket() {
let limiter = RateLimiter::with_max_tracked_keys(
NonZeroU32::new(1).unwrap(),
Duration::minutes(1),
NonZeroUsize::new(2).unwrap(),
)
.expect("valid limiter");
let start = std::time::Duration::ZERO;
assert!(limiter.check_at_elapsed("one", start).allowed);
assert!(limiter.check_at_elapsed("two", start).allowed);
assert!(limiter.check_at_elapsed("three", start).allowed);
assert!(limiter.check_at_elapsed("one", start).allowed);
assert!(limiter.inner.buckets.len() <= 2);
}
#[test]
fn auth_budgets_are_independent() {
let state = SecurityState::new(NonZeroU32::new(1).unwrap());
assert!(state.check_login("client", "user@example.test").is_ok());
assert!(state.check_registration("client").is_ok());
assert!(state.check_two_factor("client").is_ok());
assert!(state.check_password_reset("client").is_ok());
}
#[test]
fn password_reset_budget_is_bounded_per_client_address() {
let state = SecurityState::new(NonZeroU32::new(100).unwrap());
for _ in 0..5 {
assert!(state.check_password_reset("client-a").is_ok());
}
let rejection = state
.check_password_reset("client-a")
.expect_err("sixth reset attempt in one minute must be rejected");
assert_eq!(rejection.scope, super::AuthRateLimitScope::PasswordResetIp);
assert!(state.check_password_reset("client-b").is_ok());
}
#[test]
fn accepted_login_can_reset_consumed_client_and_account_budgets() {
let one = NonZeroU32::new(1).unwrap();
let state = SecurityState::with_auth_policy(
one,
AuthRateLimitPolicy {
login_ip_per_minute: one,
login_account_per_minute: one,
two_factor_ip_per_minute: one,
two_factor_account_per_minute: one,
registration_ip_per_minute: one,
},
);
assert!(state.check_login("client", "user@example.test").is_ok());
assert!(state.check_login("client", "user@example.test").is_err());
state.reset_login("client", " USER@EXAMPLE.TEST ");
assert!(state.check_login("client", "user@example.test").is_ok());
}
#[test]
fn client_keys_use_the_tcp_peer_address() {
let state = SecurityState::new(NonZeroU32::new(1).unwrap());
let peer_ip = IpAddr::V4(Ipv4Addr::new(192, 0, 2, 40));
assert_eq!(state.client_key(peer_ip), "192.0.2.40");
}
}