Debian Codegraph @

third_party/rust/neqo-transport/src/ecn.rs

raw
1 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
2 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
3 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
4 // option. This file may not be copied, modified, or distributed
5 // except according to those terms.
6
7 use std::ops::{AddAssign, Deref, DerefMut, Sub};
8
9 use enum_map::{Enum, EnumMap};
10 use neqo_common::{qdebug, qinfo, qwarn, IpTosEcn};
11
12 use crate::{
13 packet::{PacketNumber, PacketType},
14 recovery::{RecoveryToken, SentPacket},
15 Stats,
16 };
17
18 /// The number of packets to use for testing a path for ECN capability.
19 pub(crate) const TEST_COUNT: usize = 10;
20
21 /// The number of packets to use for testing a path for ECN capability when exchanging
22 /// Initials during the handshake. This is a lower number than [`TEST_COUNT`] to avoid
23 /// unnecessarily delaying the handshake; we would otherwise double the PTO [`TEST_COUNT`]
24 /// times.
25 const TEST_COUNT_INITIAL_PHASE: usize = 3;
26
27 /// The state information related to testing a path for ECN capability.
28 /// See RFC9000, Appendix A.4.
29 #[derive(Debug, PartialEq, Clone, Copy)]
30 enum ValidationState {
31 /// The path is currently being tested for ECN capability, with the number of probes sent so
32 /// far on the path during the ECN validation.
33 Testing {
34 probes_sent: usize,
35 initial_probes_acked: usize,
36 initial_probes_lost: usize,
37 },
38 /// The validation test has concluded but the path's ECN capability is not yet known.
39 Unknown,
40 /// The path is known to **not** be ECN capable.
41 Failed(ValidationError),
42 /// The path is known to be ECN capable.
43 Capable,
44 }
45
46 impl Default for ValidationState {
47 fn default() -> Self {
48 Self::Testing {
49 probes_sent: 0,
50 initial_probes_acked: 0,
51 initial_probes_lost: 0,
52 }
53 }
54 }
55
56 impl ValidationState {
57 fn set(&mut self, new: Self, stats: &mut Stats) {
58 let old = std::mem::replace(self, new);
59
60 match old {
61 Self::Testing { .. } | Self::Unknown => {}
62 Self::Failed(_) => debug_assert!(false, "Failed is a terminal state"),
63 Self::Capable => stats.ecn_path_validation[ValidationOutcome::Capable] -= 1,
64 }
65 match new {
66 Self::Testing { .. } | Self::Unknown => {}
67 Self::Failed(error) => {
68 stats.ecn_path_validation[ValidationOutcome::NotCapable(error)] += 1;
69 }
70 Self::Capable => stats.ecn_path_validation[ValidationOutcome::Capable] += 1,
71 }
72 }
73 }
74
75 /// The counts for different ECN marks.
76 ///
77 /// Note: [`Count`] is used both for outgoing UDP datagrams, returned by
78 /// remote through QUIC ACKs and for incoming UDP datagrams, read from IP TOS
79 /// header. In the former case, given that QUIC ACKs only carry
80 /// [`IpTosEcn::Ect0`], [`IpTosEcn::Ect1`] and [`IpTosEcn::Ce`], but never
81 /// [`IpTosEcn::NotEct`], the [`IpTosEcn::NotEct`] value will always be 0.
82 ///
83 /// See also <https://www.rfc-editor.org/rfc/rfc9000.html#section-19.3.2>.
84 #[derive(PartialEq, Eq, Debug, Clone, Copy, Default)]
85 pub struct Count(EnumMap<IpTosEcn, u64>);
86
87 impl Deref for Count {
88 type Target = EnumMap<IpTosEcn, u64>;
89
90 fn deref(&self) -> &Self::Target {
91 &self.0
92 }
93 }
94
95 impl DerefMut for Count {
96 fn deref_mut(&mut self) -> &mut Self::Target {
97 &mut self.0
98 }
99 }
100
101 impl Count {
102 #[must_use]
103 pub const fn new(not_ect: u64, ect0: u64, ect1: u64, ce: u64) -> Self {
104 // Yes, the enum array order is different from the argument order.
105 Self(EnumMap::from_array([not_ect, ect1, ect0, ce]))
106 }
107
108 /// Whether any of the ECT(0), ECT(1) or CE counts are non-zero.
109 #[must_use]
110 pub fn is_some(&self) -> bool {
111 self[IpTosEcn::Ect0] > 0 || self[IpTosEcn::Ect1] > 0 || self[IpTosEcn::Ce] > 0
112 }
113
114 /// Whether all of the ECN counts are zero (including Not-ECT.)
115 #[must_use]
116 pub fn is_empty(&self) -> bool {
117 self.iter().all(|(_, count)| *count == 0)
118 }
119 }
120
121 impl Sub<Self> for Count {
122 type Output = Self;
123
124 /// Subtract the ECN counts in `other` from `self`.
125 fn sub(self, rhs: Self) -> Self {
126 let mut diff = Self::default();
127 for (ecn, count) in &mut *diff {
128 *count = self[ecn].saturating_sub(rhs[ecn]);
129 }
130 diff
131 }
132 }
133
134 impl AddAssign<IpTosEcn> for Count {
135 fn add_assign(&mut self, rhs: IpTosEcn) {
136 self[rhs] += 1;
137 }
138 }
139
140 #[derive(PartialEq, Eq, Debug, Clone, Copy, Default)]
141 pub struct ValidationCount(EnumMap<ValidationOutcome, u64>);
142
143 impl Deref for ValidationCount {
144 type Target = EnumMap<ValidationOutcome, u64>;
145
146 fn deref(&self) -> &Self::Target {
147 &self.0
148 }
149 }
150
151 impl DerefMut for ValidationCount {
152 fn deref_mut(&mut self) -> &mut Self::Target {
153 &mut self.0
154 }
155 }
156
157 #[derive(Debug, Clone, Copy, Enum, PartialEq, Eq)]
158 pub enum ValidationError {
159 BlackHole,
160 Bleaching,
161 ReceivedUnsentECT1,
162 }
163
164 #[derive(Debug, Clone, Copy, Enum, PartialEq, Eq)]
165 pub enum ValidationOutcome {
166 Capable,
167 NotCapable(ValidationError),
168 }
169
170 #[derive(Debug, Default)]
171 pub(crate) struct Info {
172 /// The current state of ECN validation on this path.
173 state: ValidationState,
174
175 /// The largest ACK seen so far.
176 largest_acked: PacketNumber,
177
178 /// The ECN counts from the last ACK frame that increased `largest_acked`.
179 baseline: Count,
180 }
181
182 impl Info {
183 /// Set the baseline (= the ECN counts from the last ACK Frame).
184 pub(crate) fn set_baseline(&mut self, baseline: Count) {
185 self.baseline = baseline;
186 }
187
188 /// Expose the current baseline.
189 pub(crate) const fn baseline(&self) -> Count {
190 self.baseline
191 }
192
193 /// Count the number of packets sent out on this path during ECN validation.
194 /// Exit ECN validation if the number of packets sent exceeds `TEST_COUNT`.
195 /// We do not implement the part of the RFC that says to exit ECN validation if the time since
196 /// the start of ECN validation exceeds 3 * PTO, since this seems to happen much too quickly.
197 pub(crate) fn on_packet_sent(&mut self, stats: &mut Stats) {
198 if let ValidationState::Testing { probes_sent, .. } = &mut self.state {
199 *probes_sent += 1;
200 qdebug!("ECN probing: sent {probes_sent} probes");
201 if *probes_sent == TEST_COUNT {
202 qdebug!("ECN probing concluded with {probes_sent} probes sent");
203 self.state.set(ValidationState::Unknown, stats);
204 }
205 }
206 }
207
208 /// Disable ECN.
209 pub(crate) fn disable_ecn(&mut self, stats: &mut Stats, reason: ValidationError) {
210 self.state.set(ValidationState::Failed(reason), stats);
211 }
212
213 /// Process ECN counts from an ACK frame.
214 ///
215 /// Returns whether ECN counts contain new valid ECN CE marks.
216 pub(crate) fn on_packets_acked(
217 &mut self,
218 acked_packets: &[SentPacket],
219 ack_ecn: Option<Count>,
220 stats: &mut Stats,
221 ) -> bool {
222 let prev_baseline = self.baseline;
223
224 self.validate_ack_ecn_and_update(acked_packets, ack_ecn, stats);
225
226 matches!(self.state, ValidationState::Capable)
227 && (self.baseline - prev_baseline)[IpTosEcn::Ce] > 0
228 }
229
230 /// An [`IpTosEcn::Ect0`] marked packet has been acked.
231 pub(crate) fn acked_ecn(&mut self) {
232 if let ValidationState::Testing {
233 initial_probes_acked: probes_acked,
234 ..
235 } = &mut self.state
236 {
237 *probes_acked += 1;
238 }
239 }
240
241 /// An [`IpTosEcn::Ect0`] marked packet has been declared lost.
242 pub(crate) fn lost_ecn(&mut self, pt: PacketType, stats: &mut Stats) {
243 if pt != PacketType::Initial {
244 return;
245 }
246
247 if let ValidationState::Testing {
248 initial_probes_acked: probes_acked,
249 initial_probes_lost: probes_lost,
250 ..
251 } = &mut self.state
252 {
253 *probes_lost += 1;
254 // If we have lost all initial probes a bunch of times, we can conclude that the path
255 // is not ECN capable and likely drops all ECN marked packets.
256 if *probes_acked == 0 && *probes_lost == TEST_COUNT_INITIAL_PHASE {
257 qdebug!(
258 "ECN validation failed, all {probes_lost} initial marked packets were lost"
259 );
260 self.disable_ecn(stats, ValidationError::BlackHole);
261 }
262 }
263 }
264
265 /// After the ECN validation test has ended, check if the path is ECN capable.
266 fn validate_ack_ecn_and_update(
267 &mut self,
268 acked_packets: &[SentPacket],
269 ack_ecn: Option<Count>,
270 stats: &mut Stats,
271 ) {
272 // RFC 9000, Section 13.4.2.1:
273 //
274 // > Validating ECN counts from reordered ACK frames can result in failure. An endpoint MUST
275 // > NOT fail ECN validation as a result of processing an ACK frame that does not increase
276 // > the largest acknowledged packet number.
277 let largest_acked = acked_packets.first().expect("must be there");
278 if largest_acked.pn() <= self.largest_acked {
279 return;
280 }
281
282 // RFC 9000, Appendix A.4:
283 //
284 // > From the "unknown" state, successful validation of the ECN counts in an ACK frame
285 // > (see Section 13.4.2.1) causes the ECN state for the path to become "capable", unless
286 // > no marked packet has been acknowledged.
287 match self.state {
288 ValidationState::Testing { .. } | ValidationState::Failed(_) => return,
289 ValidationState::Unknown | ValidationState::Capable => {}
290 }
291
292 // RFC 9000, Section 13.4.2.1:
293 //
294 // > An endpoint that receives an ACK frame with ECN counts therefore validates
295 // > the counts before using them. It performs this validation by comparing newly
296 // > received counts against those from the last successfully processed ACK frame.
297 //
298 // > If an ACK frame newly acknowledges a packet that the endpoint sent with
299 // > either the ECT(0) or ECT(1) codepoint set, ECN validation fails if the
300 // > corresponding ECN counts are not present in the ACK frame.
301 let Some(ack_ecn) = ack_ecn else {
302 qwarn!("ECN validation failed, no ECN counts in ACK frame");
303 self.disable_ecn(stats, ValidationError::Bleaching);
304 return;
305 };
306 stats.ecn_tx_acked[largest_acked.packet_type()] = ack_ecn;
307
308 // We always mark with ECT(0) - if at all - so we only need to check for that.
309 //
310 // > ECN validation also fails if the sum of the increase in ECT(0) and ECN-CE counts is
311 // > less than the number of newly acknowledged packets that were originally sent with an
312 // > ECT(0) marking.
313 let newly_acked_sent_with_ect0: u64 = acked_packets
314 .iter()
315 .filter(|p| p.ecn_marked_ect0())
316 .count()
317 .try_into()
318 .expect("usize fits into u64");
319 if newly_acked_sent_with_ect0 == 0 {
320 qwarn!("ECN validation failed, no ECT(0) packets were newly acked");
321 self.disable_ecn(stats, ValidationError::Bleaching);
322 return;
323 }
324 let ecn_diff = ack_ecn - self.baseline;
325 let sum_inc = ecn_diff[IpTosEcn::Ect0] + ecn_diff[IpTosEcn::Ce];
326 if sum_inc < newly_acked_sent_with_ect0 {
327 qwarn!(
328 "ECN validation failed, ACK counted {sum_inc} new marks, but {newly_acked_sent_with_ect0} of newly acked packets were sent with ECT(0)"
329 );
330 self.disable_ecn(stats, ValidationError::Bleaching);
331 } else if ecn_diff[IpTosEcn::Ect1] > 0 {
332 qwarn!("ECN validation failed, ACK counted ECT(1) marks that were never sent");
333 self.disable_ecn(stats, ValidationError::ReceivedUnsentECT1);
334 } else if self.state != ValidationState::Capable {
335 qinfo!("ECN validation succeeded, path is capable");
336 self.state.set(ValidationState::Capable, stats);
337 }
338 self.baseline = ack_ecn;
339 self.largest_acked = largest_acked.pn();
340 }
341
342 pub(crate) const fn is_marking(&self) -> bool {
343 match self.state {
344 ValidationState::Testing { .. } | ValidationState::Capable => true,
345 ValidationState::Failed(_) | ValidationState::Unknown => false,
346 }
347 }
348
349 /// The ECN mark to use for an outgoing UDP datagram.
350 ///
351 /// On [`IpTosEcn::Ect0`] adds a [`RecoveryToken::EcnEct0`] to `tokens` in
352 /// order to detect potential loss, then handled in [`Info::lost_ecn`].
353 pub(crate) fn ecn_mark(&self, tokens: &mut Vec<RecoveryToken>) -> IpTosEcn {
354 if self.is_marking() {
355 tokens.push(RecoveryToken::EcnEct0);
356 IpTosEcn::Ect0
357 } else {
358 IpTosEcn::NotEct
359 }
360 }
361 }