1use std::{
11 borrow::Borrow,
12 collections::BTreeMap,
13 net::{IpAddr, Ipv6Addr},
14 ops::Bound::{Excluded, Included, Unbounded},
15 sync::{Arc, Mutex},
16 time::{Duration, Instant},
17};
18
19use http::StatusCode;
20use ruma::{
21 UserId,
22 api::error::{ErrorKind, LimitExceededErrorData, RetryAfter},
23};
24use tuwunel_core::{
25 Error, Result, Server, implement, smallstr::SmallString, smallvec::SmallVec, warn,
26};
27
28pub struct Service {
34 server: Arc<Server>,
35 account: Ratelimiter<AccountKey>,
36 login: Attempts,
37 uiaa: Attempts,
38}
39
40#[derive(Debug)]
46#[must_use]
47pub struct Reservation {
48 key: FailedKey,
49 hold: Hold,
50 scope: Scope,
51}
52
53type AccountKey = SmallString<[u8; 48]>;
54type FailedKey = (AccountKey, IpAddr);
55type Ratelimiter<K = String> = Mutex<Table<K>>;
56type Buckets<K> = BTreeMap<K, (Instant, f64)>;
57type Pruned<K> = SmallVec<[K; 1]>;
58
59#[derive(Default)]
60struct Attempts {
61 failed: Ratelimiter<FailedKey>,
63
64 address: Ratelimiter<IpAddr>,
66}
67
68struct Table<K = String> {
69 buckets: Buckets<K>,
70 cursor: Option<K>,
71}
72
73#[derive(Clone, Copy, Debug)]
74enum Scope {
75 Login,
76 Uiaa,
77}
78
79impl<K> Default for Table<K> {
80 fn default() -> Self { Self { buckets: BTreeMap::new(), cursor: None } }
81}
82
83impl crate::Service for Service {
84 fn build(args: &crate::Args<'_>) -> Result<Arc<Self>> {
85 Ok(Arc::new(Self {
86 server: args.server.clone(),
87 account: Ratelimiter::default(),
88 login: Attempts::default(),
89 uiaa: Attempts::default(),
90 }))
91 }
92
93 fn name(&self) -> &str { crate::service::make_name(std::module_path!()) }
94}
95
96const RATELIMIT_MAP_CAP: usize = 1 << 16;
101
102const PRUNE_SAMPLE: usize = 64;
104
105const MAX_RETRY_AFTER: Duration = Duration::from_hours(24);
107
108const FULL_WARNING_INTERVAL: Duration = Duration::from_mins(1);
110
111static FAILED_FULL_WARNING: Mutex<Option<Instant>> = Mutex::new(None);
112
113static ADDRESS_FULL_WARNING: Mutex<Option<Instant>> = Mutex::new(None);
114
115static ACCOUNT_FULL_WARNING: Mutex<Option<Instant>> = Mutex::new(None);
116
117#[cfg(test)]
118mod tests;
119
120#[derive(Clone, Copy)]
122struct Limit {
123 rate: f64,
124 burst: u32,
125}
126
127impl Limit {
128 const OFF: Self = Self { rate: 0.0, burst: 0 };
129
130 fn enabled(self) -> bool { self.burst > 0 && self.rate > 0.0 && self.rate.is_finite() }
133
134 fn burst(self) -> f64 { f64::from(self.burst) }
135}
136
137#[derive(Clone, Copy, Debug, PartialEq, Eq)]
139enum Hold {
140 Held,
142
143 Untracked,
146}
147
148#[derive(Clone, Copy, Debug)]
153enum Axis {
154 Failed,
156
157 Address,
159
160 Account,
162}
163
164impl Axis {
165 fn when_full(self) -> Result<Hold> {
166 match self {
167 | Self::Failed | Self::Address => Ok(Hold::Untracked),
168 | Self::Account => Err(limit_exceeded(None)),
169 }
170 }
171
172 fn last_full_warning(self) -> &'static Mutex<Option<Instant>> {
173 match self {
174 | Self::Failed => &FAILED_FULL_WARNING,
175 | Self::Address => &ADDRESS_FULL_WARNING,
176 | Self::Account => &ACCOUNT_FULL_WARNING,
177 }
178 }
179}
180
181#[implement(Service)]
186pub fn reserve_login_attempt(&self, user_id: &UserId, address: IpAddr) -> Result<Reservation> {
187 self.reserve_attempt(user_id, address, Scope::Login)
188}
189
190#[implement(Service)]
194pub fn reserve_uiaa_attempt(&self, user_id: &UserId, address: IpAddr) -> Result<Reservation> {
195 self.reserve_attempt(user_id, address, Scope::Uiaa)
196}
197
198#[implement(Service)]
199fn reserve_attempt(
200 &self,
201 user_id: &UserId,
202 address: IpAddr,
203 scope: Scope,
204) -> Result<Reservation> {
205 reserve_at(
206 self.attempts(scope),
207 (user_id, address),
208 (self.failed_limit(), self.address_limit(address)),
209 scope,
210 Instant::now(),
211 )
212}
213
214#[implement(Service)]
215fn attempts(&self, scope: Scope) -> &Attempts {
216 match scope {
217 | Scope::Login => &self.login,
218 | Scope::Uiaa => &self.uiaa,
219 }
220}
221
222#[implement(Service)]
227pub fn record_login(&self, reservation: Reservation) -> Result {
228 let Reservation { key, hold, scope } = reservation;
229 let now = Instant::now();
230
231 refund_at(&self.attempts(scope).failed, &key, hold, self.failed_limit(), now)?;
232 debit_at(
233 &self.account,
234 &key.0,
235 self.account_limit(),
236 Axis::Account,
237 now,
238 RATELIMIT_MAP_CAP,
239 )?;
240
241 Ok(())
242}
243
244#[implement(Service)]
249pub fn refund_login_attempt(&self, reservation: Reservation) -> Result {
250 let Reservation { key, hold, scope } = reservation;
251
252 refund_at(&self.attempts(scope).failed, &key, hold, self.failed_limit(), Instant::now())
253}
254
255#[implement(Service)]
256fn failed_limit(&self) -> Limit {
257 let failed = &self.server.config.rate_limiting.login.failed;
258
259 Limit {
260 rate: failed.per_second,
261 burst: failed.burst_count,
262 }
263}
264
265#[implement(Service)]
266fn account_limit(&self) -> Limit {
267 let account = &self.server.config.rate_limiting.login.account;
268
269 Limit {
270 rate: account.per_second,
271 burst: account.burst_count,
272 }
273}
274
275#[implement(Service)]
281fn address_limit(&self, address: IpAddr) -> Limit {
282 let config = &self.server.config;
283 let budget = &config.rate_limiting.login.address;
284 let source = config.http.ip_source.unwrap_or_default();
285
286 if !source.identifies_client(address) {
287 return Limit::OFF;
288 }
289
290 Limit {
291 rate: budget.per_second,
292 burst: budget.burst_count,
293 }
294}
295
296fn reserve_at(
297 attempts: &Attempts,
298 (user_id, address): (&UserId, IpAddr),
299 (failed, limit): (Limit, Limit),
300 scope: Scope,
301 now: Instant,
302) -> Result<Reservation> {
303 let address = address_key(address);
304
305 debit_at(&attempts.address, &address, limit, Axis::Address, now, RATELIMIT_MAP_CAP)?;
306
307 let key = (account_key(user_id), address);
308 let hold = debit_at(&attempts.failed, &key, failed, Axis::Failed, now, RATELIMIT_MAP_CAP)?;
309
310 Ok(Reservation { key, hold, scope })
311}
312
313fn address_key(address: IpAddr) -> IpAddr {
314 match address.to_canonical() {
315 | IpAddr::V4(address) => address.into(),
316 | IpAddr::V6(address) => {
317 let [a, b, c, d, ..] = address.segments();
318
319 Ipv6Addr::new(a, b, c, d, 0, 0, 0, 0).into()
320 },
321 }
322}
323
324fn account_key(user_id: &UserId) -> AccountKey {
325 let account = user_id.as_str();
326
327 if account.is_ascii() {
328 account
329 .chars()
330 .map(|ch| ch.to_ascii_lowercase())
331 .collect()
332 } else {
333 AccountKey::from_str(&account.to_lowercase())
334 }
335}
336
337fn debit_at<K, Q>(
343 table: &Ratelimiter<K>,
344 key: &Q,
345 limit: Limit,
346 axis: Axis,
347 now: Instant,
348 cap: usize,
349) -> Result<Hold>
350where
351 K: Borrow<Q> + Clone + Ord,
352 Q: Ord + ToOwned<Owned = K> + ?Sized,
353{
354 if !limit.enabled() {
355 return Ok(Hold::Untracked);
356 }
357
358 let Limit { rate, .. } = limit;
359 let burst = limit.burst();
360 let mut table = table.lock()?;
361 let Table { buckets, cursor } = &mut *table;
362
363 debug_assert!(cap > 0, "rate-limit table cap must be positive");
364
365 let Some(bucket) = buckets.get_mut(key) else {
366 if buckets.len() >= cap {
367 prune_sample(buckets, cursor, rate, burst, now);
368 }
369
370 if buckets.len() >= cap {
371 drop(table);
372 warn_table_full(axis, now);
373 return axis.when_full();
374 }
375
376 buckets.insert(key.to_owned(), (now, burst - 1.0));
377 return Ok(Hold::Held);
378 };
379
380 let (last_time, tokens) = bucket;
381 let refilled = refill(*last_time, *tokens, rate, burst, now);
382
383 if refilled < 1.0 {
384 return Err(limit_exceeded(retry_after(rate, refilled)));
385 }
386
387 *last_time = now;
388 *tokens = refilled - 1.0;
389
390 Ok(Hold::Held)
391}
392
393fn refund_at<K, Q>(
399 table: &Ratelimiter<K>,
400 key: &Q,
401 hold: Hold,
402 limit: Limit,
403 now: Instant,
404) -> Result
405where
406 K: Borrow<Q> + Ord,
407 Q: Ord + ?Sized,
408{
409 if hold == Hold::Untracked || !limit.enabled() {
410 return Ok(());
411 }
412
413 let burst = limit.burst();
414 let mut table = table.lock()?;
415 let Table { buckets, .. } = &mut *table;
416
417 let Some((last_time, tokens)) = buckets.get_mut(key) else {
418 return Ok(());
419 };
420
421 let level = burst.min(refill(*last_time, *tokens, limit.rate, burst, now) + 1.0);
422
423 if level >= burst {
424 buckets.remove(key);
425 } else {
426 *last_time = now;
427 *tokens = level;
428 }
429
430 Ok(())
431}
432
433fn refill(last: Instant, tokens: f64, rate: f64, burst: f64, now: Instant) -> f64 {
434 now.saturating_duration_since(last)
435 .as_secs_f64()
436 .mul_add(rate, tokens)
437 .min(burst)
438}
439
440fn prune_sample<K: Clone + Ord>(
448 buckets: &mut Buckets<K>,
449 cursor: &mut Option<K>,
450 rate: f64,
451 burst: f64,
452 now: Instant,
453) {
454 let after = (cursor.as_ref().map_or(Unbounded, Excluded), Unbounded);
455 let wrapped = (Unbounded, cursor.as_ref().map_or(Unbounded, Included));
456 let sample = buckets
457 .range::<K, _>(after)
458 .chain(
459 buckets
460 .range::<K, _>(wrapped)
461 .take(if cursor.is_some() { PRUNE_SAMPLE } else { 0 }),
462 )
463 .take(PRUNE_SAMPLE);
464
465 if let Some((key, _)) = sample.clone().last() {
466 match cursor {
467 | None => *cursor = Some(key.clone()),
468 | Some(cursor) => cursor.clone_from(key),
469 }
470 }
471
472 let refilled: Pruned<K> = sample
473 .filter(|(_, (last, tokens))| refill(*last, *tokens, rate, burst, now) >= burst)
474 .map(|(key, _)| key.clone())
475 .collect();
476
477 for key in refilled {
478 buckets.remove(&key);
479 }
480}
481
482fn warn_table_full(axis: Axis, now: Instant) {
487 let Ok(mut last) = axis.last_full_warning().lock() else {
488 return;
489 };
490
491 if last.is_some_and(|last| now.saturating_duration_since(last) < FULL_WARNING_INTERVAL) {
492 return;
493 }
494
495 *last = Some(now);
496
497 match axis {
498 | Axis::Failed | Axis::Address => warn!(
499 table = ?axis,
500 cap = RATELIMIT_MAP_CAP,
501 "Password rate-limit table is full of keys still being limited; attempts for \
502 keys not already in it go untracked."
503 ),
504 | Axis::Account => warn!(
505 table = ?axis,
506 cap = RATELIMIT_MAP_CAP,
507 "Login rate-limit table is full of accounts still being limited; sign-ins for \
508 accounts not already in it are refused."
509 ),
510 }
511}
512
513fn retry_after(rate: f64, tokens: f64) -> Option<Duration> {
516 let secs = ((1.0 - tokens) / rate).ceil();
517
518 Duration::try_from_secs_f64(secs.min(MAX_RETRY_AFTER.as_secs_f64())).ok()
521}
522
523fn limit_exceeded(retry_after: Option<Duration>) -> Error {
524 Error::Request(
525 ErrorKind::LimitExceeded(LimitExceededErrorData {
526 retry_after: retry_after.map(RetryAfter::Delay),
527 }),
528 "Too many password authentication attempts.".into(),
529 StatusCode::TOO_MANY_REQUESTS,
530 )
531}