Skip to main content

krot_server/
rate.rs

1//! Per-identity rate limiting (§9).
2//!
3//! Three orthogonal limits:
4//!
5//! - **Bandwidth** (bytes/s): a `governor` direct rate-limiter. Data-path
6//!   copiers call [`RateLimitState::throttle`] before each read chunk;
7//!   `governor` sleeps until the requested number of tokens is
8//!   available, which pauses reads and (transitively) engages QUIC
9//!   flow-control.
10//! - **Period quota** (bytes/period): an [`AtomicU64`] plus a rolling
11//!   reset deadline. Every chunk calls [`RateLimitState::charge`], which
12//!   increments the counter and, on cap breach, emits a `RateLimit`
13//!   frame on the identity's control stream and asks the caller to
14//!   close the data stream.
15//! - **Concurrent tunnels** — enforced elsewhere (in `session::register`
16//!   via `TunnelRegistry::count_owned_by`).
17//!
18//! Cross-core semantics (§9.2): the bandwidth bucket is per-`SharedState`
19//! (which is `Arc`'d across cores) and therefore already shared. The
20//! quota counter is a plain `AtomicU64` behind the same `Arc`, so
21//! reservation is naturally atomic across worker threads.
22
23use std::num::NonZeroU32;
24use std::sync::atomic::{AtomicU64, Ordering};
25use std::sync::{Arc, Mutex};
26use std::time::{Duration, Instant};
27
28use governor::clock::DefaultClock;
29use governor::state::{InMemoryState, NotKeyed};
30use governor::{Quota, RateLimiter};
31use tokio::io::{self, AsyncRead, AsyncReadExt, AsyncWrite, AsyncWriteExt};
32use tracing::debug;
33
34use krot_proto::{ServerFrame, TunnelId};
35
36/// The concrete governor type we hold — bytes/s direct limiter.
37type BandwidthBucket = RateLimiter<NotKeyed, InMemoryState, DefaultClock>;
38
39/// One time period. Used both for `bw=` (per-second is by far the most
40/// common but the grammar accepts anything) and `quota=`.
41#[derive(Debug, Clone, Copy, PartialEq, Eq)]
42pub enum Period {
43    Second,
44    Minute,
45    Hour,
46    Day,
47    Week,
48    /// 30-day accounting period. Matches how most operators think about
49    /// monthly bandwidth caps ("500GB/month" ≈ 500 GB per 30 days).
50    Month,
51}
52
53impl Period {
54    #[must_use]
55    pub const fn as_duration(self) -> Duration {
56        match self {
57            Self::Second => Duration::from_secs(1),
58            Self::Minute => Duration::from_secs(60),
59            Self::Hour => Duration::from_secs(60 * 60),
60            Self::Day => Duration::from_secs(24 * 60 * 60),
61            Self::Week => Duration::from_secs(7 * 24 * 60 * 60),
62            Self::Month => Duration::from_secs(30 * 24 * 60 * 60),
63        }
64    }
65}
66
67/// Parsed `<n><unit>/<period>` value from `authorized_keys`.
68#[derive(Debug, Clone, Copy, PartialEq, Eq)]
69pub struct RatePer {
70    pub bytes: u64,
71    pub period: Period,
72}
73
74impl RatePer {
75    /// Convert to bytes-per-second. Fractional seconds round *up* so a
76    /// declared cap is never silently exceeded by rounding.
77    #[must_use]
78    pub fn as_bytes_per_second(self) -> u64 {
79        let secs = self.period.as_duration().as_secs().max(1);
80        self.bytes.div_ceil(secs)
81    }
82}
83
84/// Parse `<n><unit>/<period>`, e.g. `50MB/s`, `10GB/day`, `500GB/month`.
85///
86/// Units are SI base-10 (`KB=1_000`, `MB=1_000_000`, etc.). Base-2
87/// (`KiB`, `MiB`, ...) are accepted as an operator convenience.
88#[must_use]
89pub fn parse_rate_per(s: &str) -> Option<RatePer> {
90    let (amount, period) = s.rsplit_once('/')?;
91    let period = match period.trim() {
92        "s" | "sec" | "second" => Period::Second,
93        "m" | "min" | "minute" => Period::Minute,
94        "h" | "hr" | "hour" => Period::Hour,
95        "d" | "day" => Period::Day,
96        "w" | "week" => Period::Week,
97        "mo" | "month" => Period::Month,
98        _ => return None,
99    };
100    let bytes = parse_bytes(amount.trim())?;
101    Some(RatePer { bytes, period })
102}
103
104fn parse_bytes(s: &str) -> Option<u64> {
105    // Split off the numeric prefix.
106    let split = s.find(|c: char| !c.is_ascii_digit()).unwrap_or(s.len());
107    let (num, unit) = s.split_at(split);
108    let n: u64 = num.parse().ok()?;
109    let mul: u64 = match unit.trim() {
110        "" | "B" => 1,
111        "KB" | "kB" => 1_000,
112        "KiB" => 1_024,
113        "MB" => 1_000_000,
114        "MiB" => 1_024 * 1_024,
115        "GB" => 1_000_000_000,
116        "GiB" => 1_024 * 1_024 * 1_024,
117        "TB" => 1_000_000_000_000,
118        "TiB" => 1_024_u64.pow(4),
119        _ => return None,
120    };
121    n.checked_mul(mul)
122}
123
124/// A charge outcome from [`RateLimitState::charge`].
125#[derive(Debug, Clone, Copy, PartialEq, Eq)]
126pub enum Charge {
127    /// The bytes were counted and the caller may proceed.
128    Ok,
129    /// The period quota is exhausted; the caller MUST close the stream
130    /// and stop reading. A `RateLimit` frame has been scheduled for
131    /// delivery on the control stream (if a sender is attached).
132    QuotaExceeded { retry_after_ms: u32 },
133}
134
135std::thread_local! {
136    /// §9.2 per-core rate-limit partition index. Set once at each
137    /// worker thread's startup by [`set_worker_id`]. Single-core
138    /// deployments leave it at the default `0`.
139    static WORKER_ID: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
140}
141
142/// Called by each worker thread at startup so [`RateLimitState::throttle`]
143/// picks the right per-core bucket.
144pub fn set_worker_id(id: usize) {
145    WORKER_ID.with(|w| w.set(id));
146}
147
148/// Current worker index. Zero on threads that never called
149/// [`set_worker_id`] — safe default.
150#[must_use]
151pub fn current_worker_id() -> usize {
152    WORKER_ID.with(std::cell::Cell::get)
153}
154
155/// Per-identity limits. Cheap to clone (all fields are shared / atomic).
156#[derive(Debug)]
157pub struct RateLimitState {
158    /// §9.2: N bandwidth buckets, one per worker thread. Total
159    /// aggregate rate = declared `bw=` cap, with each worker limited
160    /// to `bw / N` bytes/s. Under-utilised buckets do NOT lend
161    /// tokens to busier peers (spec allows periodic reconciliation
162    /// but we take the simpler "static partition" path). `None` when
163    /// no `bw=` cap is set.
164    ///
165    /// A single-core deployment (`n_cores = 1`) collapses to the
166    /// pre-§9.2 behaviour: one bucket at the full declared rate.
167    bw: Option<Vec<BandwidthBucket>>,
168    quota_cap: Option<u64>,
169    quota_period: Period,
170    quota_used: AtomicU64,
171    quota_reset_at: Mutex<Instant>,
172    /// mpsc sender back to the identity's live session control loop. On
173    /// quota breach a [`ServerFrame::RateLimit`] is queued here; the
174    /// session's `select!` forwards it. If no session is currently
175    /// live (dangling / not yet resumed) the send is a no-op.
176    ctrl_tx: Mutex<Option<tokio::sync::mpsc::UnboundedSender<ServerFrame>>>,
177    /// Optional link to the process-wide metrics bag. Bumped on
178    /// every [`Charge::QuotaExceeded`]. When `None` (tests) it's a
179    /// no-op — the state still works, just doesn't publish counters.
180    metrics: Option<Arc<crate::metrics::ServerMetrics>>,
181}
182
183impl RateLimitState {
184    /// Build a fresh state from an identity's `authorized_keys`
185    /// entry. `bw_partitions` is the number of worker threads the
186    /// server is running (§9.2 per-core split); passing `1`
187    /// preserves the pre-§9.2 single-bucket behaviour.
188    #[must_use]
189    pub fn from_entry(bw: Option<RatePer>, quota: Option<RatePer>, bw_partitions: usize) -> Self {
190        Self::from_entry_with_metrics(bw, quota, bw_partitions, None)
191    }
192
193    /// Same as [`Self::from_entry`] but plumbs the process-wide
194    /// metrics bag so quota breaches show up on `/admin/v1/metrics`.
195    #[must_use]
196    pub fn from_entry_with_metrics(
197        bw: Option<RatePer>,
198        quota: Option<RatePer>,
199        bw_partitions: usize,
200        metrics: Option<Arc<crate::metrics::ServerMetrics>>,
201    ) -> Self {
202        let partitions = bw_partitions.max(1);
203        let bw = bw.and_then(|r| {
204            let total_bps = r.as_bytes_per_second().min(u64::from(u32::MAX));
205            // Split the total rate evenly across workers. Aggregate
206            // ceiling stays at `total_bps` (partitions * per_core_bps),
207            // matching the declared cap.
208            let per_core_bps = (total_bps / partitions as u64).max(1);
209            let bps = NonZeroU32::new(per_core_bps as u32)?;
210            let mut buckets = Vec::with_capacity(partitions);
211            for _ in 0..partitions {
212                buckets.push(RateLimiter::direct(Quota::per_second(bps)));
213            }
214            Some(buckets)
215        });
216        let (quota_cap, quota_period) = match quota {
217            Some(q) => (Some(q.bytes), q.period),
218            None => (None, Period::Month),
219        };
220        Self {
221            bw,
222            quota_cap,
223            quota_period,
224            quota_used: AtomicU64::new(0),
225            quota_reset_at: Mutex::new(Instant::now() + quota_period.as_duration()),
226            ctrl_tx: Mutex::new(None),
227            metrics,
228        }
229    }
230
231    /// Install a fresh control-stream sender. Called at session start,
232    /// replacing any leftover sender from a prior session for the same
233    /// identity.
234    pub fn attach_ctrl(&self, tx: tokio::sync::mpsc::UnboundedSender<ServerFrame>) {
235        *self.ctrl_tx.lock().unwrap() = Some(tx);
236    }
237
238    /// Detach the current control-stream sender. Called at session end.
239    pub fn detach_ctrl(&self) {
240        *self.ctrl_tx.lock().unwrap() = None;
241    }
242
243    /// Await bandwidth-bucket tokens for `n` bytes, blocking as needed.
244    ///
245    /// If no `bw=` cap is set this is a no-op. On a multi-worker
246    /// runtime the current thread's [`current_worker_id`] picks
247    /// which per-core partition to spend tokens against (§9.2).
248    pub async fn throttle(&self, n: u32) {
249        let Some(buckets) = &self.bw else { return };
250        let Some(n) = NonZeroU32::new(n) else { return };
251        let idx = current_worker_id() % buckets.len();
252        let bw = &buckets[idx];
253        // until_n_ready cannot fail when n <= burst; governor sizes the
254        // burst to the per-second quota. Larger single-shot reads simply
255        // wait as many intervals as needed.
256        if let Err(_e) = bw.until_n_ready(n).await {
257            // Insufficient burst capacity: fall back to per-token wait
258            // by looping. Practically unreachable with our default
259            // Quota::per_second which has burst == quota.
260            for _ in 0..n.get() {
261                bw.until_ready().await;
262            }
263        }
264    }
265
266    /// Account `n` bytes against the period quota. Rolls the counter
267    /// over automatically at the reset deadline. On breach a
268    /// `RateLimit` frame is queued for the control stream and
269    /// [`Charge::QuotaExceeded`] is returned.
270    pub fn charge(&self, tunnel_id: TunnelId, n: u64) -> Charge {
271        let Some(cap) = self.quota_cap else {
272            return Charge::Ok;
273        };
274        // Roll the counter if the reset instant has passed.
275        {
276            let mut deadline = self.quota_reset_at.lock().unwrap();
277            let now = Instant::now();
278            if now >= *deadline {
279                self.quota_used.store(0, Ordering::Relaxed);
280                *deadline = now + self.quota_period.as_duration();
281            }
282        }
283        let prev = self.quota_used.fetch_add(n, Ordering::Relaxed);
284        if prev + n > cap {
285            let retry_after_ms = self.retry_after_ms();
286            // Notify the session loop. Failure to send (no live
287            // session) is fine — nothing observes the queued frame
288            // and the data stream is closed anyway.
289            if let Some(tx) = self.ctrl_tx.lock().unwrap().as_ref() {
290                let _ = tx.send(ServerFrame::RateLimit {
291                    tunnel_id: Some(tunnel_id),
292                    retry_after_ms,
293                });
294            }
295            if let Some(m) = &self.metrics {
296                m.rate_limit_quota_exceeded.fetch_add(1, Ordering::Relaxed);
297            }
298            return Charge::QuotaExceeded { retry_after_ms };
299        }
300        Charge::Ok
301    }
302
303    /// Bytes currently counted against the period quota. Used by the
304    /// §16.4 admin API's `/metrics` endpoint.
305    #[must_use]
306    pub fn quota_used_snapshot(&self) -> u64 {
307        self.quota_used.load(Ordering::Relaxed)
308    }
309
310    /// Millis until the current quota period resets. Clamped to
311    /// `u32::MAX` to fit `RateLimit.retry_after_ms`.
312    #[must_use]
313    pub fn retry_after_ms(&self) -> u32 {
314        let now = Instant::now();
315        let deadline = *self.quota_reset_at.lock().unwrap();
316        let d = deadline.saturating_duration_since(now);
317        u32::try_from(d.as_millis()).unwrap_or(u32::MAX)
318    }
319}
320
321/// Bidirectional byte-shovel that meters both directions against a
322/// shared [`RateLimitState`]. Each chunk read on either side is
323/// (1) throttled against the bandwidth bucket, then (2) charged
324/// against the period quota, then (3) forwarded to the peer.
325///
326/// `first_byte_deadline` enforces §10: if NO byte flows in either
327/// direction within the deadline, the streams are dropped and
328/// `io::ErrorKind::TimedOut` is returned. Once at least one byte has
329/// flowed (in either direction) the deadline no longer applies.
330///
331/// Returns `(a_to_b, b_to_a)` byte counts. Terminates cleanly on EOF,
332/// or with `io::ErrorKind::Other` on quota exhaustion (the peer has
333/// already been half-closed).
334pub async fn run_metered<A, B>(
335    a: A,
336    b: B,
337    rate: &RateLimitState,
338    tunnel_id: TunnelId,
339    first_byte_deadline: Duration,
340) -> io::Result<(u64, u64)>
341where
342    A: AsyncRead + AsyncWrite + Unpin,
343    B: AsyncRead + AsyncWrite + Unpin,
344{
345    use std::sync::atomic::AtomicBool;
346    let seen_any = Arc::new(AtomicBool::new(false));
347    let (a_r, a_w) = tokio::io::split(a);
348    let (b_r, b_w) = tokio::io::split(b);
349    let (n_ab, n_ba) = tokio::try_join!(
350        shovel(
351            a_r,
352            b_w,
353            rate,
354            tunnel_id,
355            first_byte_deadline,
356            Arc::clone(&seen_any)
357        ),
358        shovel(
359            b_r,
360            a_w,
361            rate,
362            tunnel_id,
363            first_byte_deadline,
364            Arc::clone(&seen_any)
365        ),
366    )?;
367    Ok((n_ab, n_ba))
368}
369
370async fn shovel<R, W>(
371    mut r: R,
372    mut w: W,
373    rate: &RateLimitState,
374    tunnel_id: TunnelId,
375    first_byte_deadline: Duration,
376    seen_any: Arc<std::sync::atomic::AtomicBool>,
377) -> io::Result<u64>
378where
379    R: AsyncRead + Unpin,
380    W: AsyncWrite + Unpin,
381{
382    use std::sync::atomic::Ordering as AtomicOrdering;
383    let mut buf = vec![0u8; 16 * 1024];
384    let mut total = 0u64;
385    let mut first = true;
386    loop {
387        let n = if first && !seen_any.load(AtomicOrdering::Relaxed) {
388            // §10 first-byte deadline — applies only until either
389            // direction has moved bytes.
390            if let Ok(res) = tokio::time::timeout(first_byte_deadline, r.read(&mut buf)).await {
391                res?
392            } else if seen_any.load(AtomicOrdering::Relaxed) {
393                // Peer direction already saw bytes; retry without
394                // deadline.
395                r.read(&mut buf).await?
396            } else {
397                return Err(io::Error::new(
398                    io::ErrorKind::TimedOut,
399                    "data-stream first-byte deadline exceeded",
400                ));
401            }
402        } else {
403            r.read(&mut buf).await?
404        };
405        first = false;
406        if n == 0 {
407            let _ = w.shutdown().await;
408            return Ok(total);
409        }
410        seen_any.store(true, AtomicOrdering::Relaxed);
411        // Bandwidth throttle first — this awaits token availability.
412        rate.throttle(u32::try_from(n).unwrap_or(u32::MAX)).await;
413        // Quota check.
414        match rate.charge(tunnel_id, n as u64) {
415            Charge::Ok => {}
416            Charge::QuotaExceeded { retry_after_ms } => {
417                debug!(?tunnel_id, retry_after_ms, "quota exceeded, closing stream");
418                let _ = w.shutdown().await;
419                return Err(io::Error::other("period quota exceeded"));
420            }
421        }
422        w.write_all(&buf[..n]).await?;
423        total += n as u64;
424    }
425}
426
427#[cfg(test)]
428mod tests {
429    use super::*;
430    use krot_proto::TunnelId;
431
432    #[test]
433    fn parses_bw() {
434        let r = parse_rate_per("50MB/s").unwrap();
435        assert_eq!(r.bytes, 50_000_000);
436        assert_eq!(r.period, Period::Second);
437        assert_eq!(r.as_bytes_per_second(), 50_000_000);
438    }
439
440    #[test]
441    fn parses_quota() {
442        let r = parse_rate_per("500GB/month").unwrap();
443        assert_eq!(r.bytes, 500_000_000_000);
444        assert_eq!(r.period, Period::Month);
445    }
446
447    #[test]
448    fn parses_units() {
449        assert_eq!(parse_rate_per("1KiB/s").unwrap().bytes, 1024);
450        assert_eq!(parse_rate_per("1MiB/s").unwrap().bytes, 1024 * 1024);
451        assert_eq!(parse_rate_per("2GB/day").unwrap().bytes, 2_000_000_000);
452    }
453
454    #[test]
455    fn rejects_bogus() {
456        assert!(parse_rate_per("garbage").is_none());
457        assert!(parse_rate_per("50MB").is_none());
458        assert!(parse_rate_per("50MB/yr").is_none());
459    }
460
461    #[test]
462    fn quota_exhausts_and_reports_retry() {
463        let state = RateLimitState::from_entry(
464            None,
465            Some(RatePer {
466                bytes: 100,
467                period: Period::Second,
468            }),
469            1,
470        );
471        assert!(matches!(state.charge(TunnelId(1), 60), Charge::Ok));
472        // 60 + 60 > 100 — should trip.
473        let c = state.charge(TunnelId(1), 60);
474        assert!(matches!(c, Charge::QuotaExceeded { .. }), "got {c:?}");
475    }
476
477    #[test]
478    fn no_quota_is_always_ok() {
479        let state = RateLimitState::from_entry(None, None, 1);
480        for _ in 0..1000 {
481            assert!(matches!(state.charge(TunnelId(1), 1_000_000), Charge::Ok));
482        }
483    }
484
485    #[test]
486    fn bw_partitions_split_evenly() {
487        // 4 workers, 400 B/s cap → each worker gets 100 B/s bucket.
488        let state = RateLimitState::from_entry(
489            Some(RatePer {
490                bytes: 400,
491                period: Period::Second,
492            }),
493            None,
494            4,
495        );
496        let Some(buckets) = state.bw.as_ref() else {
497            panic!("expected bw buckets");
498        };
499        assert_eq!(buckets.len(), 4);
500    }
501
502    #[test]
503    fn bw_partitions_zero_treated_as_one() {
504        // Defensive: 0 workers should still produce 1 bucket at full
505        // rate rather than divide-by-zero panic.
506        let state = RateLimitState::from_entry(
507            Some(RatePer {
508                bytes: 100,
509                period: Period::Second,
510            }),
511            None,
512            0,
513        );
514        let buckets = state.bw.as_ref().unwrap();
515        assert_eq!(buckets.len(), 1);
516    }
517
518    #[test]
519    fn worker_id_thread_local_isolates() {
520        set_worker_id(7);
521        assert_eq!(current_worker_id(), 7);
522        // A fresh thread starts at 0 (default).
523        std::thread::spawn(|| {
524            assert_eq!(current_worker_id(), 0);
525        })
526        .join()
527        .unwrap();
528        // The setter is scoped to this thread.
529        assert_eq!(current_worker_id(), 7);
530    }
531}