1use core::fmt;
14use core::time::Duration;
15
16use super::Instant;
17
18#[derive(Clone, Copy, Debug, PartialEq, Eq)]
34pub struct RateLimit {
35 count: u32,
36 period: Duration,
37 burst: u32,
38}
39
40impl RateLimit {
41 pub const fn new(count: u32, period: Duration) -> Result<Self, InvalidRateLimit> {
47 if count == 0 {
48 return Err(InvalidRateLimit::ZeroCount);
49 }
50 if period.as_micros() == 0 {
51 return Err(InvalidRateLimit::ZeroPeriod);
52 }
53 Ok(Self {
54 count,
55 period,
56 burst: count,
57 })
58 }
59
60 pub const fn per_second(count: u32) -> Result<Self, InvalidRateLimit> {
66 Self::new(count, Duration::from_secs(1))
67 }
68
69 pub const fn per_minute(count: u32) -> Result<Self, InvalidRateLimit> {
75 Self::new(count, Duration::from_secs(60))
76 }
77
78 pub const fn with_burst(mut self, burst: u32) -> Result<Self, InvalidRateLimit> {
88 if burst == 0 {
89 return Err(InvalidRateLimit::ZeroBurst);
90 }
91 self.burst = burst;
92 Ok(self)
93 }
94
95 #[must_use]
97 pub const fn count(&self) -> u32 {
98 self.count
99 }
100
101 #[must_use]
103 pub const fn period(&self) -> Duration {
104 self.period
105 }
106
107 #[must_use]
109 pub const fn burst(&self) -> u32 {
110 self.burst
111 }
112
113 fn interval_micros(&self) -> u64 {
116 let period = u64::try_from(self.period.as_micros()).unwrap_or(u64::MAX);
117 (period / u64::from(self.count)).max(1)
118 }
119}
120
121impl fmt::Display for RateLimit {
122 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
123 let period = self.period;
124 if period == Duration::from_secs(60) {
125 write!(f, "{}/min", self.count)?;
126 } else if period == Duration::from_secs(1) {
127 write!(f, "{}/s", self.count)?;
128 } else {
129 write!(f, "{} per {}ms", self.count, period.as_millis())?;
130 }
131 write!(f, " (burst {})", self.burst)
132 }
133}
134
135#[derive(Clone, Copy, Debug, PartialEq, Eq)]
137#[non_exhaustive]
138pub enum InvalidRateLimit {
139 ZeroCount,
141 ZeroPeriod,
143 ZeroBurst,
145}
146
147impl fmt::Display for InvalidRateLimit {
148 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
149 f.write_str(match self {
150 Self::ZeroCount => "a message rate needs a count of at least 1",
151 Self::ZeroPeriod => "a message rate needs a period of at least 1µs",
152 Self::ZeroBurst => "a message rate needs a burst of at least 1",
153 })
154 }
155}
156
157#[cfg(feature = "std")]
158impl std::error::Error for InvalidRateLimit {}
159
160#[derive(Clone, Copy, Debug)]
163pub(super) struct Gcra {
164 interval: u64,
165 tolerance: u64,
166 tat: u64,
167 limited: bool,
169}
170
171#[derive(Clone, Copy, Debug, PartialEq, Eq)]
173pub(super) enum Admission {
174 Admitted,
176 Refused { new_episode: bool },
178}
179
180impl Gcra {
181 pub(super) fn new(limit: RateLimit) -> Self {
182 let interval = limit.interval_micros();
183 Self {
184 interval,
185 tolerance: interval.saturating_mul(u64::from(limit.burst)),
186 tat: 0,
187 limited: false,
188 }
189 }
190
191 pub(super) fn admit(&mut self, now: Instant) -> Admission {
196 let now = now.as_millis().saturating_mul(1000);
197 let tat = self.tat.max(now);
198 if tat.saturating_add(self.interval) - now > self.tolerance {
199 let new_episode = !self.limited;
200 self.limited = true;
201 return Admission::Refused { new_episode };
202 }
203 self.tat = tat.saturating_add(self.interval);
204 self.limited = false;
205 Admission::Admitted
206 }
207}
208
209#[cfg(test)]
210mod tests {
211 use super::*;
212
213 fn at(millis: u64) -> Instant {
214 Instant::from_millis(millis)
215 }
216
217 #[test]
218 fn a_burst_is_admitted_and_the_next_one_is_not() {
219 let mut gcra = Gcra::new(RateLimit::per_minute(60).unwrap().with_burst(5).unwrap());
220 for _ in 0..5 {
221 assert_eq!(gcra.admit(at(0)), Admission::Admitted);
222 }
223 assert_eq!(gcra.admit(at(0)), Admission::Refused { new_episode: true });
224 assert_eq!(gcra.admit(at(0)), Admission::Refused { new_episode: false });
225 }
226
227 #[test]
228 fn one_interval_later_one_more_is_admitted() {
229 let mut gcra = Gcra::new(RateLimit::per_minute(60).unwrap().with_burst(1).unwrap());
230 assert_eq!(gcra.admit(at(0)), Admission::Admitted);
231 assert!(matches!(gcra.admit(at(999)), Admission::Refused { .. }));
232 assert_eq!(gcra.admit(at(1000)), Admission::Admitted);
233 assert_eq!(
235 gcra.admit(at(1000)),
236 Admission::Refused { new_episode: true }
237 );
238 }
239
240 #[test]
241 fn a_flood_does_not_push_the_peer_into_debt() {
242 let mut gcra = Gcra::new(RateLimit::per_second(1).unwrap());
243 assert_eq!(gcra.admit(at(0)), Admission::Admitted);
244 for _ in 0..10_000 {
245 let _ = gcra.admit(at(10));
246 }
247 assert_eq!(gcra.admit(at(1000)), Admission::Admitted);
248 }
249
250 #[test]
251 fn the_sustained_rate_holds_over_time() {
252 let mut gcra = Gcra::new(RateLimit::per_second(10).unwrap().with_burst(1).unwrap());
253 let admitted = (0..10_000u64)
254 .filter(|ms| gcra.admit(at(*ms)) == Admission::Admitted)
255 .count();
256 assert_eq!(admitted, 100);
258 }
259
260 #[test]
261 fn zeros_are_refused_and_extremes_do_not_overflow() {
262 assert_eq!(RateLimit::per_second(0), Err(InvalidRateLimit::ZeroCount));
263 assert_eq!(
264 RateLimit::new(1, Duration::from_nanos(999)),
265 Err(InvalidRateLimit::ZeroPeriod)
266 );
267 assert_eq!(
268 RateLimit::per_second(1).unwrap().with_burst(0),
269 Err(InvalidRateLimit::ZeroBurst)
270 );
271 let mut huge = Gcra::new(
272 RateLimit::new(u32::MAX, Duration::MAX)
273 .unwrap()
274 .with_burst(u32::MAX)
275 .unwrap(),
276 );
277 assert_eq!(huge.admit(at(u64::MAX)), Admission::Admitted);
278 let mut fast = Gcra::new(RateLimit::new(u32::MAX, Duration::from_micros(1)).unwrap());
279 assert_eq!(fast.admit(at(0)), Admission::Admitted);
280 }
281
282 #[test]
283 fn it_renders_for_a_log() {
284 let rate = RateLimit::per_minute(120).unwrap().with_burst(20).unwrap();
285 assert_eq!(rate.to_string(), "120/min (burst 20)");
286 }
287}