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}