Skip to main content

tor_proto/
congestion.rs

1//! Congestion control subsystem.
2//!
3//! This object is attached to a circuit hop (CircHop) and controls the logic for the congestion
4//! control support of the Tor Network. It also manages the circuit level SENDME logic which is
5//! part of congestion control.
6//!
7//! # Implementation
8//!
9//! The basics of this subsystem is that it is notified when a DATA cell is received or sent. This
10//! in turn updates the congestion control state so that the very important
11//! [`can_send`](CongestionControl::can_send) function be accurate to decide if a DATA cell can be
12//! sent or not.
13//!
14//! Any part of the arti code that wants to send a DATA cell on the wire needs to call
15//! [`can_send`](CongestionControl::can_send) before else we'll risk leaving the circuit in a
16//! protocol violation state.
17//!
18//! Furthermore, as we receive and emit SENDMEs, it also has entry point for those two events in
19//! order to update the state.
20
21#[cfg(test)]
22pub(crate) mod test_utils;
23
24mod fixed;
25pub mod params;
26mod rtt;
27pub(crate) mod sendme;
28mod vegas;
29
30use crate::{Error, Result};
31
32use self::{
33    params::{Algorithm, CongestionControlParams, CongestionWindowParams},
34    rtt::{ClockStall, RoundtripTimeEstimator},
35    sendme::SendmeValidator,
36};
37use tor_cell::relaycell::msg::SendmeTag;
38use tor_rtcompat::{DynTimeProvider, SleepProvider};
39
40use std::task::{Context, Poll, Waker};
41
42/// This trait defines what a congestion control algorithm must implement in order to interface
43/// with the circuit reactor.
44///
45/// Note that all functions informing the algorithm, as in not getters, return a Result meaning
46/// that on error, it means we can't recover or that there is a protocol violation. In both
47/// cases, the circuit MUST be closed.
48pub(crate) trait CongestionControlAlgorithm: Send + std::fmt::Debug {
49    /// Return true iff this algorithm uses stream level SENDMEs.
50    fn uses_stream_sendme(&self) -> bool;
51    /// Return true iff this algorithm uses stream level XON/XOFFs.
52    fn uses_xon_xoff(&self) -> bool;
53    /// Return true iff the next cell is expected to be a SENDME.
54    fn is_next_cell_sendme(&self) -> bool;
55    /// Return true iff a cell can be sent on the wire according to the congestion control
56    /// algorithm.
57    fn can_send(&self) -> bool;
58    /// Return the congestion window object. The reason is returns an Option is because not all
59    /// algorithm uses one and so we avoid acting on it if so.
60    fn cwnd(&self) -> Option<CongestionWindow>;
61
62    /// Inform the algorithm that we just got a DATA cell.
63    ///
64    /// Return true if a SENDME should be sent immediately or false if not.
65    fn data_received(&mut self) -> Result<bool>;
66    /// Inform the algorithm that we just sent a DATA cell.
67    fn data_sent(&mut self) -> Result<()>;
68    /// Inform the algorithm that we've just received a SENDME.
69    ///
70    /// This is a core function because the algorithm massively update its state when receiving a
71    /// SENDME by using the RTT value and congestion signals.
72    fn sendme_received(
73        &mut self,
74        state: &mut State,
75        rtt: &mut RoundtripTimeEstimator,
76        signals: CongestionSignals,
77        clock_stall: ClockStall,
78    ) -> Result<()>;
79    /// Inform the algorithm that we just sent a SENDME.
80    fn sendme_sent(&mut self) -> Result<()>;
81
82    /// Return the number of in-flight cells (sent but awaiting SENDME ack).
83    ///
84    /// Optional, because not all algorithms track this.
85    #[cfg(feature = "conflux")]
86    fn inflight(&self) -> Option<u32>;
87
88    /// Test Only: Return the congestion window.
89    #[cfg(test)]
90    fn send_window(&self) -> u32;
91
92    /// Return the congestion control [`Algorithm`] implemented by this type.
93    fn algorithm(&self) -> Algorithm;
94}
95
96/// These are congestion signals used by a congestion control algorithm to make decisions. These
97/// signals are various states of our internals. This is not an exhaustive list.
98#[derive(Copy, Clone)]
99pub(crate) struct CongestionSignals {
100    /// Indicate if the channel is blocked.
101    pub(crate) channel_blocked: bool,
102    /// The size of the channel outbound queue.
103    pub(crate) channel_outbound_size: u32,
104}
105
106impl CongestionSignals {
107    /// Constructor
108    pub(crate) fn new(channel_blocked: bool, channel_outbound_size: usize) -> Self {
109        Self {
110            channel_blocked,
111            channel_outbound_size: channel_outbound_size.saturating_add(0) as u32,
112        }
113    }
114}
115
116/// Congestion control state.
117#[derive(Copy, Clone, Default)]
118pub(crate) enum State {
119    /// The initial state any circuit starts in. Used to gradually increase the amount of data
120    /// being transmitted in order to converge towards to optimal capacity.
121    #[default]
122    SlowStart,
123    /// Steady state representing what we think is optimal. This is always after slow start.
124    Steady,
125}
126
127impl State {
128    /// Return true iff this is SlowStart.
129    pub(crate) fn in_slow_start(&self) -> bool {
130        matches!(self, State::SlowStart)
131    }
132}
133
134/// A congestion window. This is generic for all algorithms but their parameters' value will differ
135/// depending on the selected algorithm.
136#[derive(Clone, Copy, Debug)]
137pub(crate) struct CongestionWindow {
138    /// Congestion window parameters from the consensus.
139    params: CongestionWindowParams,
140    /// The actual value of our congestion window.
141    value: u32,
142    /// The congestion window is full.
143    is_full: bool,
144}
145
146impl CongestionWindow {
147    /// Constructor taking consensus parameters.
148    fn new(params: CongestionWindowParams) -> Self {
149        Self {
150            value: params.cwnd_init(),
151            params,
152            is_full: false,
153        }
154    }
155
156    /// Decrement the window by the increment value.
157    pub(crate) fn dec(&mut self) {
158        self.value = self
159            .value
160            .saturating_sub(self.increment())
161            .max(self.params.cwnd_min());
162    }
163
164    /// Increment the window by the increment value.
165    pub(crate) fn inc(&mut self) {
166        self.value = self
167            .value
168            .saturating_add(self.increment())
169            .min(self.params.cwnd_max());
170    }
171
172    /// Return the current value.
173    pub(crate) fn get(&self) -> u32 {
174        self.value
175    }
176
177    /// Return the expected rate for which the congestion window should be updated at.
178    ///
179    /// See `CWND_UPDATE_RATE` in prop324.
180    pub(crate) fn update_rate(&self, state: &State) -> u32 {
181        if state.in_slow_start() {
182            1
183        } else {
184            (self.get() + self.increment_rate() * self.sendme_inc() / 2)
185                / (self.increment_rate() * self.sendme_inc())
186        }
187    }
188
189    /// Return minimum value of the congestion window.
190    pub(crate) fn min(&self) -> u32 {
191        self.params.cwnd_min()
192    }
193
194    /// Set the congestion window value with a new value.
195    pub(crate) fn set(&mut self, value: u32) {
196        self.value = value;
197    }
198
199    /// Return the increment value.
200    pub(crate) fn increment(&self) -> u32 {
201        self.params.cwnd_inc()
202    }
203
204    /// Return the rate at which we should increment the window.
205    pub(crate) fn increment_rate(&self) -> u32 {
206        self.params.cwnd_inc_rate()
207    }
208
209    /// Return true iff this congestion window is full.
210    pub(crate) fn is_full(&self) -> bool {
211        self.is_full
212    }
213
214    /// Reset the full flag meaning it is now not full.
215    pub(crate) fn reset_full(&mut self) {
216        self.is_full = false;
217    }
218
219    /// Return the number of expected SENDMEs per congestion window.
220    ///
221    /// Spec: prop324 SENDME_PER_CWND definition
222    pub(crate) fn sendme_per_cwnd(&self) -> u32 {
223        (self.get() + (self.sendme_inc() / 2)) / self.sendme_inc()
224    }
225
226    /// Return the RFC3742 slow start increment value.
227    ///
228    /// Spec: prop324 rfc3742_ss_inc definition
229    pub(crate) fn rfc3742_ss_inc(&mut self, ss_cap: u32) -> u32 {
230        let inc = if self.get() <= ss_cap {
231            ((self.params.cwnd_inc_pct_ss().as_percent() * self.sendme_inc()) + 50) / 100
232        } else {
233            (((self.sendme_inc() * ss_cap) + self.get()) / (self.get() * 2)).max(1)
234        };
235        self.value += inc;
236        inc
237    }
238
239    /// Evaluate the fullness of the window with the given parameters.
240    ///
241    /// Spec: prop324 see cwnd_is_full and cwnd_is_nonfull definition.
242    /// C-tor: cwnd_became_full() and cwnd_became_nonfull()
243    pub(crate) fn eval_fullness(&mut self, inflight: u32, full_gap: u32, full_minpct: u32) {
244        if (inflight + (self.sendme_inc() * full_gap)) >= self.get() {
245            self.is_full = true;
246        } else if (100 * inflight) < (full_minpct * self.get()) {
247            self.is_full = false;
248        }
249    }
250
251    /// Return the SENDME increment value.
252    pub(crate) fn sendme_inc(&self) -> u32 {
253        self.params.sendme_inc().into()
254    }
255
256    /// Return the congestion window params.
257    #[cfg(any(test, feature = "conflux"))]
258    pub(crate) fn params(&self) -> &CongestionWindowParams {
259        &self.params
260    }
261}
262
263/// Congestion control state of a hop on a circuit.
264///
265/// This controls the entire logic of congestion control and circuit level SENDMEs.
266pub(crate) struct CongestionControl {
267    /// Which congestion control state are we in?
268    state: State,
269    /// This is the SENDME validator as in it keeps track of the circuit tag found within an
270    /// authenticated SENDME cell. It can store the tags and validate a tag against our queue of
271    /// expected values.
272    sendme_validator: SendmeValidator<SendmeTag>,
273    /// The RTT estimator for the circuit we are attached on.
274    rtt: RoundtripTimeEstimator,
275    /// The congestion control algorithm.
276    algorithm: Box<dyn CongestionControlAlgorithm>,
277    /// The waker of the last [`poll_can_send`](Self::poll_can_send) invocation.
278    ///
279    /// We only remember the latest waker, because `poll_can_send()` is expected
280    /// to be called from the `StreamReactor`, where there is only ever a single
281    /// task waiting to be woken when `can_send()` is `true`.
282    ///
283    // Note: if the implementation grows more complex, and we end up using this
284    // from multiple places, or find ourselves needing to store multiple wakers,
285    // we should consider replacing this with something less hacky.
286    waker: Option<Waker>,
287}
288
289impl CongestionControl {
290    /// Construct a new CongestionControl
291    pub(crate) fn new(params: &CongestionControlParams) -> Self {
292        let state = State::default();
293        // Use what the consensus tells us to use.
294        let algorithm: Box<dyn CongestionControlAlgorithm> = match params.alg() {
295            Algorithm::FixedWindow(p) => Box::new(fixed::FixedWindow::new(*p)),
296            Algorithm::Vegas(p) => {
297                let cwnd = CongestionWindow::new(params.cwnd_params());
298                Box::new(vegas::Vegas::new(*p, &state, cwnd))
299            }
300        };
301        Self {
302            algorithm,
303            rtt: RoundtripTimeEstimator::new(params.rtt_params()),
304            sendme_validator: SendmeValidator::new(),
305            state,
306            waker: None,
307        }
308    }
309
310    /// Return true iff the underlying algorithm uses stream level SENDMEs.
311    /// At the moment, only FixedWindow uses it. It has been eliminated with Vegas.
312    pub(crate) fn uses_stream_sendme(&self) -> bool {
313        self.algorithm.uses_stream_sendme()
314    }
315
316    /// Return true iff the underlying algorithm uses stream level XON/XOFFs.
317    /// At the moment, only Vegas uses it.
318    pub(crate) fn uses_xon_xoff(&self) -> bool {
319        self.algorithm.uses_xon_xoff()
320    }
321
322    /// Helper for checking if [`can_send()`](Self::can_send) is `true` from
323    /// an asynchronous context.
324    ///
325    /// This function arranges for the waker to be woken when a SENDME cell
326    /// is received.
327    ///
328    /// Important: only one waker can be registered at a time.
329    /// If a waker is already registered, calling this function again
330    /// will cause the existing waker to be dropped.
331    ///
332    /// Returns `Poll::Pending` if `can_send` is false `false`.
333    pub(crate) fn poll_can_send(&mut self, cx: &mut Context<'_>) -> Poll<()> {
334        if self.can_send() {
335            Poll::Ready(())
336        } else {
337            // Note: this discards the previous waker, if there was one
338            self.waker = Some(cx.waker().clone());
339            Poll::Pending
340        }
341    }
342
343    /// Return true iff a DATA cell is allowed to be sent based on the congestion control state.
344    pub(crate) fn can_send(&self) -> bool {
345        self.algorithm.can_send()
346    }
347
348    /// Called when a SENDME cell is received.
349    ///
350    /// An error is returned if there is a protocol violation with regards to congestion control.
351    ///
352    /// This wakes the waker registered with [`poll_can_send`](Self::poll_can_send),
353    /// if there is one.
354    pub(crate) fn note_sendme_received(
355        &mut self,
356        runtime: &DynTimeProvider,
357        tag: SendmeTag,
358        signals: CongestionSignals,
359    ) -> Result<()> {
360        // This MUST be the first thing that we do that is validate the SENDME. Any error leads to
361        // closing the circuit.
362        self.sendme_validator.validate(Some(tag))?;
363
364        let now = runtime.now();
365        // Update our RTT estimate if the algorithm yields back a congestion window. RTT
366        // measurements only make sense for a congestion window. For example, FixedWindow here
367        // doesn't use it and so no need for the RTT.
368        let clock_stall = if let Some(cwnd) = self.algorithm.cwnd() {
369            self.rtt
370                .update(now, &self.state, &cwnd)
371                .map_err(|e| Error::CircProto(e.to_string()))?
372        } else {
373            ClockStall::NotDetected
374        };
375
376        // Notify the algorithm that we've received a SENDME.
377        self.algorithm
378            .sendme_received(&mut self.state, &mut self.rtt, signals, clock_stall)?;
379
380        // The SENDME might have changed the congestion window and so wake up any wakers
381        // that might be waiting on this update.
382        if let Some(waker) = self.waker.take() {
383            waker.wake();
384        }
385
386        Ok(())
387    }
388
389    /// Called when a SENDME cell is sent.
390    pub(crate) fn note_sendme_sent(&mut self) -> Result<()> {
391        self.algorithm.sendme_sent()
392    }
393
394    /// Called when a DATA cell is received.
395    ///
396    /// Returns true iff a SENDME should be sent false otherwise. An error is returned if there is
397    /// a protocol violation with regards to flow or congestion control.
398    pub(crate) fn note_data_received(&mut self) -> Result<bool> {
399        self.algorithm.data_received()
400    }
401
402    /// Called when a DATA cell is sent.
403    ///
404    /// An error is returned if there is a protocol violation with regards to flow or congestion
405    /// control.
406    pub(crate) fn note_data_sent<U>(&mut self, runtime: &DynTimeProvider, tag: &U) -> Result<()>
407    where
408        U: Clone + Into<SendmeTag>,
409    {
410        // Inform the algorithm that the data was just sent. This is important to be the very first
411        // thing so the congestion window can be updated accordingly making the following calls
412        // using the latest data.
413        self.algorithm.data_sent()?;
414
415        // If next cell is a SENDME, we need to record the tag of this cell in order to validate
416        // the next SENDME when it arrives.
417        if self.algorithm.is_next_cell_sendme() {
418            self.sendme_validator.record(tag);
419            // Only keep the SENDME timestamp if the algorithm has a congestion window.
420            if self.algorithm.cwnd().is_some() {
421                self.rtt.expect_sendme(runtime.now());
422            }
423        }
424
425        Ok(())
426    }
427
428    /// Return the number of in-flight cells (sent but awaiting SENDME ack).
429    ///
430    /// Optional, because not all algorithms track this.
431    #[cfg(feature = "conflux")]
432    pub(crate) fn inflight(&self) -> Option<u32> {
433        self.algorithm.inflight()
434    }
435
436    /// Return the congestion window object.
437    ///
438    /// Optional, because not all algorithms track this.
439    #[cfg(feature = "conflux")]
440    pub(crate) fn cwnd(&self) -> Option<CongestionWindow> {
441        self.algorithm.cwnd()
442    }
443
444    /// Return a reference to the RTT estimator.
445    pub(crate) fn rtt(&self) -> &RoundtripTimeEstimator {
446        &self.rtt
447    }
448
449    /// Return the congestion control algorithm.
450    #[cfg(feature = "conflux")]
451    pub(crate) fn algorithm(&self) -> Algorithm {
452        self.algorithm.algorithm()
453    }
454}
455
456#[cfg(test)]
457mod test {
458    // @@ begin test lint list maintained by maint/add_warning @@
459    #![allow(clippy::bool_assert_comparison)]
460    #![allow(clippy::clone_on_copy)]
461    #![allow(clippy::dbg_macro)]
462    #![allow(clippy::mixed_attributes_style)]
463    #![allow(clippy::print_stderr)]
464    #![allow(clippy::print_stdout)]
465    #![allow(clippy::single_char_pattern)]
466    #![allow(clippy::unwrap_used)]
467    #![allow(clippy::unchecked_time_subtraction)]
468    #![allow(clippy::useless_vec)]
469    #![allow(clippy::needless_pass_by_value)]
470    #![allow(clippy::string_slice)] // See arti#2571
471    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
472
473    use crate::congestion::test_utils::new_cwnd;
474
475    use super::CongestionControl;
476    use tor_cell::relaycell::msg::SendmeTag;
477
478    impl CongestionControl {
479        /// For testing: get a copy of the current send window, and the
480        /// expected incoming tags.
481        pub(crate) fn send_window_and_expected_tags(&self) -> (u32, Vec<SendmeTag>) {
482            (
483                self.algorithm.send_window(),
484                self.sendme_validator.expected_tags(),
485            )
486        }
487    }
488
489    #[test]
490    fn test_cwnd() {
491        let mut cwnd = new_cwnd();
492
493        // Validate the getters are coherent with initialization.
494        assert_eq!(cwnd.get(), cwnd.params().cwnd_init());
495        assert_eq!(cwnd.min(), cwnd.params().cwnd_min());
496        assert_eq!(cwnd.increment(), cwnd.params().cwnd_inc());
497        assert_eq!(cwnd.increment_rate(), cwnd.params().cwnd_inc_rate());
498        assert_eq!(cwnd.sendme_inc(), u32::from(cwnd.params().sendme_inc()));
499        assert!(!cwnd.is_full());
500
501        // Validate changes.
502        cwnd.inc();
503        assert_eq!(
504            cwnd.get(),
505            cwnd.params().cwnd_init() + cwnd.params().cwnd_inc()
506        );
507        cwnd.dec();
508        assert_eq!(cwnd.get(), cwnd.params().cwnd_init());
509    }
510}