use std::{
collections::HashMap,
hash::Hash,
net::{IpAddr, Ipv6Addr},
time::Instant,
};
pub(crate) fn network_of(ip: IpAddr) -> IpAddr {
masked(ip, 64)
}
#[cfg(any(feature = "relay", test))]
pub(crate) fn prefix_of(ip: IpAddr) -> IpAddr {
masked(ip, 48)
}
#[cfg(any(feature = "relay", test))]
pub(crate) fn heaviest_prefixes(
entries: impl Iterator<Item = IpAddr>,
newcomer: IpAddr,
) -> Vec<IpAddr> {
let mut counts: HashMap<IpAddr, usize> = HashMap::new();
for prefix in entries {
*counts.entry(prefix).or_default() += 1;
}
let max = counts.values().copied().max().unwrap_or(0);
if counts.get(&newcomer).copied().unwrap_or(0) >= max {
return vec![newcomer];
}
counts
.into_iter()
.filter(|&(_, n)| n == max)
.map(|(prefix, _)| prefix)
.collect()
}
fn masked(ip: IpAddr, bits: u32) -> IpAddr {
match ip {
IpAddr::V4(_) => ip,
IpAddr::V6(v6) => match v6.to_ipv4_mapped() {
Some(v4) => IpAddr::V4(v4),
None => IpAddr::V6(Ipv6Addr::from(u128::from(v6) & (u128::MAX << (128 - bits)))),
},
}
}
pub(crate) struct RateLimiter<K = IpAddr> {
buckets: HashMap<K, (Instant, f64)>,
max_pps: f64,
burst: f64,
max_keys: usize,
ticks: u32,
}
const PRUNE_INTERVAL_TICKS: u32 = 48;
impl<K: Hash + Eq + Clone> RateLimiter<K> {
pub(crate) fn new(max_pps: f64, burst: f64) -> Self {
Self {
buckets: HashMap::new(),
max_pps,
burst,
max_keys: usize::MAX,
ticks: 0,
}
}
#[cfg(any(feature = "security", test))]
pub(crate) fn capped(mut self, max_keys: usize) -> Self {
self.max_keys = max_keys;
self
}
pub(crate) fn allow(&mut self, key: K) -> bool {
let now = Instant::now();
if self.buckets.len() >= self.max_keys
&& !self.buckets.contains_key(&key)
&& let Some(oldest) = self
.buckets
.iter()
.min_by_key(|(_, (last, _))| *last)
.map(|(k, _)| k.clone())
{
self.buckets.remove(&oldest);
}
let (last, tokens) = self.buckets.entry(key).or_insert((now, self.burst));
let elapsed = now.duration_since(*last).as_secs_f64();
*tokens = (*tokens + self.max_pps * elapsed).min(self.burst);
*last = now;
if *tokens >= 1.0 {
*tokens -= 1.0;
true
} else {
false
}
}
pub(crate) fn tick_prune(&mut self) {
self.ticks += 1;
if !self.ticks.is_multiple_of(PRUNE_INTERVAL_TICKS) {
return;
}
if let Some(cutoff) = Instant::now().checked_sub(std::time::Duration::from_mins(1)) {
self.buckets.retain(|_, (last, _)| *last > cutoff);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn networks_and_prefixes() {
let a: IpAddr = "2001:db8:1:2:aaaa::1".parse().unwrap();
let b: IpAddr = "2001:db8:1:2:bbbb::2".parse().unwrap();
let c: IpAddr = "2001:db8:1:3::1".parse().unwrap();
let d: IpAddr = "2001:db8:2::1".parse().unwrap();
assert_eq!(network_of(a), network_of(b));
assert_ne!(network_of(a), network_of(c));
assert_eq!(prefix_of(a), prefix_of(c), "same /48");
assert_ne!(prefix_of(a), prefix_of(d));
let mapped: IpAddr = "::ffff:198.51.100.7".parse().unwrap();
let v4: IpAddr = "198.51.100.7".parse().unwrap();
assert_eq!((network_of(mapped), prefix_of(mapped)), (v4, v4));
}
#[test]
fn a_full_capped_limiter_forgets_its_oldest_key() {
let mut limiter = RateLimiter::<u32>::new(0.0, 1.0).capped(2);
assert!(limiter.allow(1));
assert!(limiter.allow(2));
assert!(!limiter.allow(2), "known keys keep their own budget");
assert!(
limiter.allow(3),
"a new key is never locked out by a full map"
);
assert_eq!(limiter.buckets.len(), 2);
assert!(
!limiter.buckets.contains_key(&1),
"the oldest key made room"
);
}
#[test]
fn heaviest_prefixes_break_ties_together() {
let ip = |s: &str| s.parse::<IpAddr>().unwrap();
let (a, b, c) = (ip("192.0.2.1"), ip("192.0.2.2"), ip("192.0.2.3"));
assert_eq!(heaviest_prefixes([a, a, b].into_iter(), c), vec![a]);
assert_eq!(
heaviest_prefixes([a, a, b].into_iter(), a),
vec![a],
"pays itself"
);
let mut tied = heaviest_prefixes([a, a, b, b, c].into_iter(), c);
tied.sort();
assert_eq!(tied, vec![a, b]);
}
}