quiche/recovery/congestion/
mod.rs

1// Copyright (C) 2024, Cloudflare, Inc.
2// All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8//     * Redistributions of source code must retain the above copyright notice,
9//       this list of conditions and the following disclaimer.
10//
11//     * Redistributions in binary form must reproduce the above copyright
12//       notice, this list of conditions and the following disclaimer in the
13//       documentation and/or other materials provided with the distribution.
14//
15// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
16// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
17// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
19// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27use std::time::Instant;
28
29use self::recovery::Acked;
30use super::bandwidth::Bandwidth;
31use super::RecoveryConfig;
32use super::Sent;
33use crate::recovery::rtt;
34use crate::recovery::rtt::RttStats;
35use crate::recovery::CongestionControlAlgorithm;
36use crate::StartupExit;
37use crate::StartupExitReason;
38
39pub struct SsThresh {
40    // Current slow start threshold.  Defaults to usize::MAX which
41    // indicates we're still in the initial slow start phase.
42    ssthresh: usize,
43
44    // Information about the slow start exit, if it already happened.
45    // Set on the first call to update().
46    startup_exit: Option<StartupExit>,
47}
48
49impl Default for SsThresh {
50    fn default() -> Self {
51        Self {
52            ssthresh: usize::MAX,
53            startup_exit: None,
54        }
55    }
56}
57
58impl SsThresh {
59    fn get(&self) -> usize {
60        self.ssthresh
61    }
62
63    fn startup_exit(&self) -> Option<StartupExit> {
64        self.startup_exit
65    }
66
67    fn update(&mut self, ssthresh: usize, in_css: bool) {
68        if self.startup_exit.is_none() {
69            let reason = if in_css {
70                // Exit happened in conservative slow start, attribute
71                // the exit to CSS.
72                StartupExitReason::ConservativeSlowStartRounds
73            } else {
74                // In normal slow start, attribute the exit to loss.
75                StartupExitReason::Loss
76            };
77            self.startup_exit = Some(StartupExit::new(ssthresh, None, reason));
78        }
79        self.ssthresh = ssthresh;
80    }
81}
82
83pub struct Congestion {
84    // Congestion control.
85    pub(crate) cc_ops: &'static CongestionControlOps,
86
87    cubic_state: cubic::State,
88
89    // HyStart++.
90    pub(crate) hystart: hystart::Hystart,
91
92    // RFC6937 PRR.
93    pub(crate) prr: prr::PRR,
94
95    // The maximum size of a data aggregate scheduled and
96    // transmitted together.
97    send_quantum: usize,
98
99    pub(crate) congestion_window: usize,
100
101    pub(crate) ssthresh: SsThresh,
102
103    bytes_acked_sl: usize,
104
105    bytes_acked_ca: usize,
106
107    pub(crate) congestion_recovery_start_time: Option<Instant>,
108
109    pub(crate) app_limited: bool,
110
111    pub(crate) delivery_rate: delivery_rate::Rate,
112
113    /// Initial congestion window size in terms of packet count.
114    pub(crate) initial_congestion_window_packets: usize,
115
116    max_datagram_size: usize,
117
118    pub(crate) lost_count: usize,
119
120    pub(crate) enable_cubic_idle_restart_fix: bool,
121}
122
123impl Congestion {
124    pub(crate) fn from_config(recovery_config: &RecoveryConfig) -> Self {
125        let initial_congestion_window = recovery_config.max_send_udp_payload_size *
126            recovery_config.initial_congestion_window_packets;
127
128        let mut cc = Congestion {
129            congestion_window: initial_congestion_window,
130
131            ssthresh: Default::default(),
132
133            bytes_acked_sl: 0,
134
135            bytes_acked_ca: 0,
136
137            congestion_recovery_start_time: None,
138
139            cc_ops: recovery_config.cc_algorithm.into(),
140
141            cubic_state: cubic::State::default(),
142
143            app_limited: false,
144
145            lost_count: 0,
146
147            initial_congestion_window_packets: recovery_config
148                .initial_congestion_window_packets,
149
150            max_datagram_size: recovery_config.max_send_udp_payload_size,
151
152            send_quantum: initial_congestion_window,
153
154            delivery_rate: delivery_rate::Rate::default(),
155
156            hystart: hystart::Hystart::new(recovery_config.hystart),
157
158            prr: prr::PRR::default(),
159
160            enable_cubic_idle_restart_fix: recovery_config
161                .enable_cubic_idle_restart_fix,
162        };
163
164        (cc.cc_ops.on_init)(&mut cc);
165
166        cc
167    }
168
169    pub(crate) fn in_congestion_recovery(&self, sent_time: Instant) -> bool {
170        match self.congestion_recovery_start_time {
171            Some(congestion_recovery_start_time) =>
172                sent_time <= congestion_recovery_start_time,
173
174            None => false,
175        }
176    }
177
178    /// The most recent data delivery rate estimate.
179    pub(crate) fn delivery_rate(&self) -> Bandwidth {
180        self.delivery_rate.sample_delivery_rate()
181    }
182
183    pub(crate) fn send_quantum(&self) -> usize {
184        self.send_quantum
185    }
186
187    pub(crate) fn congestion_window(&self) -> usize {
188        self.congestion_window
189    }
190
191    fn update_app_limited(&mut self, v: bool) {
192        self.app_limited = v;
193    }
194
195    #[allow(clippy::too_many_arguments)]
196    pub(crate) fn on_packet_sent(
197        &mut self, bytes_in_flight: usize, sent_bytes: usize, now: Instant,
198        pkt: &mut Sent, bytes_lost: u64, in_flight: bool,
199    ) {
200        if in_flight {
201            self.update_app_limited(
202                (bytes_in_flight + sent_bytes) < self.congestion_window,
203            );
204
205            (self.cc_ops.on_packet_sent)(self, sent_bytes, bytes_in_flight, now);
206
207            self.prr.on_packet_sent(sent_bytes);
208
209            // HyStart++: Start of the round in a slow start.
210            if self.hystart.enabled() &&
211                self.congestion_window < self.ssthresh.get()
212            {
213                self.hystart.start_round(pkt.pkt_num);
214            }
215        }
216
217        pkt.time_sent = now;
218
219        // bytes_in_flight is already updated. Use previous value.
220        self.delivery_rate
221            .on_packet_sent(pkt, bytes_in_flight, bytes_lost);
222    }
223
224    pub(crate) fn on_packets_acked(
225        &mut self, bytes_in_flight: usize, acked: &mut Vec<Acked>,
226        rtt_stats: &RttStats, now: Instant,
227    ) {
228        // Update delivery rate sample per acked packet.
229        for pkt in acked.iter() {
230            self.delivery_rate.update_rate_sample(pkt, now);
231        }
232
233        // Fill in a rate sample.
234        self.delivery_rate.generate_rate_sample(*rtt_stats.min_rtt);
235
236        // Call congestion control hooks.
237        (self.cc_ops.on_packets_acked)(
238            self,
239            bytes_in_flight,
240            acked,
241            now,
242            rtt_stats,
243        );
244    }
245}
246
247pub(crate) struct CongestionControlOps {
248    pub on_init: fn(r: &mut Congestion),
249
250    pub on_packet_sent: fn(
251        r: &mut Congestion,
252        sent_bytes: usize,
253        bytes_in_flight: usize,
254        now: Instant,
255    ),
256
257    pub on_packets_acked: fn(
258        r: &mut Congestion,
259        bytes_in_flight: usize,
260        packets: &mut Vec<Acked>,
261        now: Instant,
262        rtt_stats: &RttStats,
263    ),
264
265    pub congestion_event: fn(
266        r: &mut Congestion,
267        bytes_in_flight: usize,
268        lost_bytes: usize,
269        largest_lost_packet: &Sent,
270        now: Instant,
271    ),
272
273    pub checkpoint: fn(r: &mut Congestion),
274
275    pub rollback: fn(r: &mut Congestion) -> bool,
276
277    #[cfg(feature = "qlog")]
278    pub state_str: fn(r: &Congestion, now: Instant) -> &'static str,
279
280    pub debug_fmt: fn(
281        r: &Congestion,
282        formatter: &mut std::fmt::Formatter,
283    ) -> std::fmt::Result,
284}
285
286impl From<CongestionControlAlgorithm> for &'static CongestionControlOps {
287    fn from(algo: CongestionControlAlgorithm) -> Self {
288        match algo {
289            CongestionControlAlgorithm::Reno => &reno::RENO,
290            CongestionControlAlgorithm::CUBIC => &cubic::CUBIC,
291            // Bbr2Gcongestion is routed to the congestion implementation in
292            // the gcongestion directory by Recovery::new_with_config;
293            // LegacyRecovery never gets a RecoveryConfig with the
294            // Bbr2Gcongestion algorithm.
295            CongestionControlAlgorithm::Bbr2Gcongestion => unreachable!(),
296        }
297    }
298}
299
300#[cfg(test)]
301mod tests {
302    use super::*;
303
304    #[test]
305    fn ssthresh_init() {
306        let ssthresh: SsThresh = Default::default();
307        assert_eq!(ssthresh.get(), usize::MAX);
308        assert_eq!(ssthresh.startup_exit(), None);
309    }
310
311    #[test]
312    fn ssthresh_in_css() {
313        let expected_startup_exit = StartupExit::new(
314            1000,
315            None,
316            StartupExitReason::ConservativeSlowStartRounds,
317        );
318        let mut ssthresh: SsThresh = Default::default();
319        ssthresh.update(1000, true);
320        assert_eq!(ssthresh.get(), 1000);
321        assert_eq!(ssthresh.startup_exit(), Some(expected_startup_exit));
322
323        ssthresh.update(2000, true);
324        assert_eq!(ssthresh.get(), 2000);
325        // startup_exit is only updated on the first update.
326        assert_eq!(ssthresh.startup_exit(), Some(expected_startup_exit));
327
328        ssthresh.update(500, false);
329        assert_eq!(ssthresh.get(), 500);
330        assert_eq!(ssthresh.startup_exit(), Some(expected_startup_exit));
331    }
332
333    #[test]
334    fn ssthresh_in_slow_start() {
335        let expected_startup_exit =
336            StartupExit::new(1000, None, StartupExitReason::Loss);
337        let mut ssthresh: SsThresh = Default::default();
338        ssthresh.update(1000, false);
339        assert_eq!(ssthresh.get(), 1000);
340        assert_eq!(ssthresh.startup_exit(), Some(expected_startup_exit));
341
342        ssthresh.update(2000, true);
343        assert_eq!(ssthresh.get(), 2000);
344        // startup_exit is only updated on the first update.
345        assert_eq!(ssthresh.startup_exit(), Some(expected_startup_exit));
346
347        ssthresh.update(500, false);
348        assert_eq!(ssthresh.get(), 500);
349        assert_eq!(ssthresh.startup_exit(), Some(expected_startup_exit));
350    }
351}
352
353mod cubic;
354mod delivery_rate;
355mod hystart;
356mod prr;
357pub(crate) mod recovery;
358mod reno;
359
360#[cfg(test)]
361mod test_sender;
quiche/recovery/congestion/mod.rs

quiche/recovery/congestion/
mod.rs
