use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::net::{IpAddr, SocketAddr};
use std::time::{Duration, Instant};
struct FixedWindowMap<K> {
window: Duration,
max_keys: usize,
hits: HashMap<K, (Instant, u32)>,
}
impl<K: Eq + Hash + Copy> FixedWindowMap<K> {
fn new(window: Duration, max_keys: usize) -> Self {
Self {
window,
max_keys: max_keys.max(1),
hits: HashMap::new(),
}
}
fn can_allow(&self, key: K, max_per_window: u32) -> bool {
let now = Instant::now();
if let Some(entry) = self.hits.get(&key) {
if now.duration_since(entry.0) >= self.window {
return true;
}
return entry.1 < max_per_window;
}
true
}
fn can_consume(&self, key: K, amount: u32, max_per_window: u32) -> bool {
if amount > max_per_window {
return false;
}
let now = Instant::now();
if let Some(entry) = self.hits.get(&key) {
if now.duration_since(entry.0) >= self.window {
return true;
}
return entry.1.saturating_add(amount) <= max_per_window;
}
true
}
fn allow(&mut self, key: K, max_per_window: u32) -> bool {
let now = Instant::now();
if let Some(entry) = self.hits.get_mut(&key) {
if now.duration_since(entry.0) >= self.window {
*entry = (now, 1);
return true;
}
if entry.1 >= max_per_window {
return false;
}
entry.1 = entry.1.saturating_add(1);
return true;
}
if self.hits.len() >= self.max_keys {
if let Some(victim) = self
.hits
.iter()
.find(|(_, (start, _))| now.duration_since(*start) >= self.window)
.map(|(k, _)| *k)
.or_else(|| self.hits.keys().next().copied())
{
self.hits.remove(&victim);
}
}
self.hits.insert(key, (now, 1));
true
}
fn consume(&mut self, key: K, amount: u32, max_per_window: u32) -> bool {
let now = Instant::now();
if let Some(entry) = self.hits.get_mut(&key) {
if now.duration_since(entry.0) >= self.window {
if amount > max_per_window {
return false;
}
*entry = (now, amount);
return true;
}
if entry.1.saturating_add(amount) > max_per_window {
return false;
}
entry.1 = entry.1.saturating_add(amount);
return true;
}
if amount > max_per_window {
return false;
}
if self.hits.len() >= self.max_keys {
if let Some(victim) = self
.hits
.iter()
.find(|(_, (start, _))| now.duration_since(*start) >= self.window)
.map(|(k, _)| *k)
.or_else(|| self.hits.keys().next().copied())
{
self.hits.remove(&victim);
}
}
self.hits.insert(key, (now, amount));
true
}
fn prune(&mut self) {
let now = Instant::now();
self.hits
.retain(|_, (start, _)| now.duration_since(*start) < self.window * 2);
}
}
pub struct UdpRateLimit {
global: FixedWindowMap<()>,
per_ip: FixedWindowMap<IpAddr>,
global_max: u32,
per_ip_max: u32,
}
impl UdpRateLimit {
pub fn new(per_ip_max: u32) -> Self {
Self::with_limits(512, per_ip_max, 4096)
}
pub fn with_limits(global_max: u32, per_ip_max: u32, max_tracked_ips: usize) -> Self {
let window = Duration::from_secs(1);
Self {
global: FixedWindowMap::new(window, 1),
per_ip: FixedWindowMap::new(window, max_tracked_ips),
global_max: global_max.max(1),
per_ip_max: per_ip_max.max(1),
}
}
pub fn allow(&mut self, ip: IpAddr) -> bool {
if !self.per_ip.can_allow(ip, self.per_ip_max) {
return false;
}
if !self.global.can_allow((), self.global_max) {
return false;
}
let _ = self.per_ip.allow(ip, self.per_ip_max);
self.global.allow((), self.global_max)
}
pub fn prune(&mut self) {
self.global.prune();
self.per_ip.prune();
}
}
pub struct ReplyBudget {
global: FixedWindowMap<()>,
per_dest: FixedWindowMap<DestKey>,
global_bytes: u32,
per_dest_bytes: u32,
}
#[derive(Clone, Copy, Eq, PartialEq)]
struct DestKey(u64);
impl Hash for DestKey {
fn hash<H: Hasher>(&self, state: &mut H) {
self.0.hash(state);
}
}
fn dest_key(addr: SocketAddr) -> DestKey {
let mut hasher = std::collections::hash_map::DefaultHasher::new();
addr.hash(&mut hasher);
DestKey(hasher.finish())
}
impl ReplyBudget {
pub fn new() -> Self {
Self::with_limits(256 * 1024, 8 * 1024, 4096)
}
pub fn with_limits(global_bytes: u32, per_dest_bytes: u32, max_dests: usize) -> Self {
let window = Duration::from_secs(1);
Self {
global: FixedWindowMap::new(window, 1),
per_dest: FixedWindowMap::new(window, max_dests),
global_bytes: global_bytes.max(1),
per_dest_bytes: per_dest_bytes.max(1),
}
}
pub fn allow_reply(&mut self, addr: SocketAddr, bytes: usize) -> bool {
let amount = u32::try_from(bytes).unwrap_or(u32::MAX);
let dest = dest_key(addr);
if !self.per_dest.can_consume(dest, amount, self.per_dest_bytes) {
return false;
}
if !self.global.can_consume((), amount, self.global_bytes) {
return false;
}
let _ = self.per_dest.consume(dest, amount, self.per_dest_bytes);
self.global.consume((), amount, self.global_bytes)
}
pub fn prune(&mut self) {
self.global.prune();
self.per_dest.prune();
}
}
impl Default for ReplyBudget {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::net::{Ipv4Addr, SocketAddrV4};
#[test]
fn enforces_per_ip_cap() {
let mut lim = UdpRateLimit::with_limits(10_000, 3, 64);
let ip = IpAddr::V4(Ipv4Addr::new(1, 2, 3, 4));
assert!(lim.allow(ip));
assert!(lim.allow(ip));
assert!(lim.allow(ip));
assert!(!lim.allow(ip));
}
#[test]
fn enforces_global_ingress_cap() {
let mut lim = UdpRateLimit::with_limits(2, 100, 64);
assert!(lim.allow(IpAddr::V4(Ipv4Addr::new(1, 0, 0, 1))));
assert!(lim.allow(IpAddr::V4(Ipv4Addr::new(1, 0, 0, 2))));
assert!(!lim.allow(IpAddr::V4(Ipv4Addr::new(1, 0, 0, 3))));
}
#[test]
fn bounds_tracked_ips() {
let mut lim = UdpRateLimit::with_limits(10_000, 1, 2);
assert!(lim.allow(IpAddr::V4(Ipv4Addr::new(1, 0, 0, 1))));
assert!(lim.allow(IpAddr::V4(Ipv4Addr::new(1, 0, 0, 2))));
assert!(lim.allow(IpAddr::V4(Ipv4Addr::new(1, 0, 0, 3))));
assert_eq!(lim.per_ip.hits.len(), 2);
}
#[test]
fn reply_budget_caps_destination() {
let mut budget = ReplyBudget::with_limits(10_000, 100, 64);
let addr = SocketAddr::V4(SocketAddrV4::new(Ipv4Addr::new(8, 8, 8, 8), 6881));
assert!(budget.allow_reply(addr, 60));
assert!(budget.allow_reply(addr, 40));
assert!(!budget.allow_reply(addr, 1));
}
}