Debian Codegraph @

third_party/rust/neqo-transport/src/recovery/mod.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 // Tracking of sent packets and detecting their loss.
8
9 #![allow(
10 clippy::module_name_repetitions,
11 reason = "<https://github.com/mozilla/neqo/issues/2284#issuecomment-2782711813>"
12 )]
13
14 #[cfg(feature = "bench")]
15 pub mod sent;
16 #[cfg(not(feature = "bench"))]
17 mod sent;
18 mod token;
19
20 use std::{
21 cmp::{max, min},
22 fmt::{self, Display, Formatter},
23 ops::RangeInclusive,
24 time::{Duration, Instant},
25 };
26
27 use enum_map::EnumMap;
28 use enumset::enum_set;
29 use neqo_common::{qdebug, qinfo, qlog::NeqoQlog, qtrace, qwarn};
30 pub use sent::SentPacket;
31 use sent::SentPackets;
32 use strum::IntoEnumIterator as _;
33 pub use token::{RecoveryToken, StreamRecoveryToken};
34
35 use crate::{
36 ecn,
37 packet::PacketNumber,
38 path::{Path, PathRef},
39 qlog::{self, QlogMetric},
40 rtt::{RttEstimate, RttSource},
41 stats::{Stats, StatsCell},
42 tracking::{PacketNumberSpace, PacketNumberSpaceSet},
43 };
44
45 pub const PACKET_THRESHOLD: u64 = 3;
46 /// `ACK_ONLY_SIZE_LIMIT` is the minimum size of the congestion window.
47 /// If the congestion window is this small, we will only send ACK frames.
48 pub const ACK_ONLY_SIZE_LIMIT: usize = 256;
49 /// The maximum number of packets we send on a PTO.
50 pub const MAX_PTO_PACKET_COUNT: usize = 2;
51 /// The preferred limit on the number of packets that are tracked.
52 /// If we exceed this number, we start sending `PING` frames sooner to
53 /// force the peer to acknowledge some of them.
54 pub const MAX_OUTSTANDING_UNACK: usize = 200;
55 /// Disable PING until this many packets are outstanding.
56 pub const MIN_OUTSTANDING_UNACK: usize = 16;
57 /// The scale we use for the fast PTO feature.
58 pub const FAST_PTO_SCALE: u8 = 100;
59
60 /// `SendProfile` tells a sender how to send packets.
61 #[derive(Debug)]
62 pub struct SendProfile {
63 /// The limit on the size of the packet.
64 limit: usize,
65 /// Whether this is a PTO, and what space the PTO is for.
66 pto: Option<PacketNumberSpace>,
67 /// What spaces should be probed.
68 probe: PacketNumberSpaceSet,
69 /// Whether pacing is active.
70 paced: bool,
71 }
72
73 impl SendProfile {
74 #[must_use]
75 pub fn new_limited(limit: usize) -> Self {
76 // When the limit is too low, we only send ACK frames.
77 // Set the limit to `ACK_ONLY_SIZE_LIMIT - 1` to ensure that
78 // ACK-only packets are still limited in size.
79 Self {
80 limit: max(ACK_ONLY_SIZE_LIMIT - 1, limit),
81 pto: None,
82 probe: PacketNumberSpaceSet::default(),
83 paced: false,
84 }
85 }
86
87 #[must_use]
88 pub fn new_paced() -> Self {
89 // When pacing, we still allow ACK frames to be sent.
90 Self {
91 limit: ACK_ONLY_SIZE_LIMIT - 1,
92 pto: None,
93 probe: PacketNumberSpaceSet::default(),
94 paced: true,
95 }
96 }
97
98 #[must_use]
99 pub fn new_pto(pn_space: PacketNumberSpace, mtu: usize, probe: PacketNumberSpaceSet) -> Self {
100 debug_assert!(mtu > ACK_ONLY_SIZE_LIMIT);
101 debug_assert!(probe.contains(pn_space));
102 Self {
103 limit: mtu,
104 pto: Some(pn_space),
105 probe,
106 paced: false,
107 }
108 }
109
110 /// Whether probing this space is helpful. This isn't necessarily the space
111 /// that caused the timer to pop, but it is helpful to send a PING in a space
112 /// that has the PTO timer armed.
113 #[must_use]
114 pub fn should_probe(&self, space: PacketNumberSpace) -> bool {
115 self.probe.contains(space)
116 }
117
118 /// Determine whether an ACK-only packet should be sent for the given packet
119 /// number space.
120 /// Send only ACKs either: when the space available is too small, or when a PTO
121 /// exists for a later packet number space (which should get the most space).
122 #[must_use]
123 pub fn ack_only(&self, space: PacketNumberSpace) -> bool {
124 self.limit < ACK_ONLY_SIZE_LIMIT || self.pto.is_some_and(|sp| space < sp)
125 }
126
127 #[must_use]
128 pub const fn paced(&self) -> bool {
129 self.paced
130 }
131
132 #[must_use]
133 pub const fn limit(&self) -> usize {
134 self.limit
135 }
136 }
137
138 #[derive(Debug)]
139 pub struct LossRecoverySpace {
140 space: PacketNumberSpace,
141 largest_acked: Option<PacketNumber>,
142 largest_acked_sent_time: Option<Instant>,
143 /// The time used to calculate the PTO timer for this space.
144 /// This is the time that the last ACK-eliciting packet in this space
145 /// was sent. This might be the time that a probe was sent.
146 last_ack_eliciting: Option<Instant>,
147 /// The number of outstanding packets in this space that are in flight.
148 /// This might be less than the number of ACK-eliciting packets,
149 /// because PTO packets don't count.
150 in_flight_outstanding: usize,
151 /// The packets that we have sent and are tracking.
152 sent_packets: SentPackets,
153 /// The time that the first out-of-order packet was sent.
154 /// This is `None` if there were no out-of-order packets detected.
155 /// When set to `Some(T)`, time-based loss detection should be enabled.
156 first_ooo_time: Option<Instant>,
157 }
158
159 impl LossRecoverySpace {
160 #[must_use]
161 pub fn new(space: PacketNumberSpace) -> Self {
162 Self {
163 space,
164 largest_acked: None,
165 largest_acked_sent_time: None,
166 last_ack_eliciting: None,
167 in_flight_outstanding: 0,
168 sent_packets: SentPackets::default(),
169 first_ooo_time: None,
170 }
171 }
172
173 /// Find the time we sent the first packet that is lower than the
174 /// largest acknowledged and that isn't yet declared lost.
175 /// Use the value we prepared earlier in `detect_lost_packets`.
176 #[must_use]
177 pub const fn loss_recovery_timer_start(&self) -> Option<Instant> {
178 self.first_ooo_time
179 }
180
181 #[must_use]
182 pub const fn in_flight_outstanding(&self) -> bool {
183 self.in_flight_outstanding > 0
184 }
185
186 pub fn pto_packets(&mut self) -> impl Iterator<Item = &SentPacket> {
187 self.sent_packets.iter_mut().filter_map(|sent| {
188 sent.pto().then(|| {
189 qtrace!("PTO: marking packet {} lost ", sent.pn());
190 &*sent
191 })
192 })
193 }
194
195 #[must_use]
196 pub fn pto_base_time(&self) -> Option<Instant> {
197 if self.in_flight_outstanding() {
198 debug_assert!(self.last_ack_eliciting.is_some());
199 self.last_ack_eliciting
200 } else if self.space == PacketNumberSpace::ApplicationData {
201 None
202 } else {
203 // Nasty special case to prevent handshake deadlocks.
204 // A client needs to keep the PTO timer armed to prevent a stall
205 // of the handshake. Technically, this has to stop once we receive
206 // an ACK of Handshake or 1-RTT, or when we receive HANDSHAKE_DONE,
207 // but a few extra probes won't hurt.
208 // It only means that we fail anti-amplification tests.
209 // A server shouldn't arm its PTO timer this way. The server sends
210 // ack-eliciting, in-flight packets immediately so this only
211 // happens when the server has nothing outstanding. If we had
212 // client authentication, this might cause some extra probes,
213 // but they would be harmless anyway.
214 self.last_ack_eliciting
215 }
216 }
217
218 pub fn on_packet_sent(&mut self, sent_packet: SentPacket) {
219 if sent_packet.ack_eliciting() {
220 self.last_ack_eliciting = Some(sent_packet.time_sent());
221 self.in_flight_outstanding += 1;
222 } else if self.space != PacketNumberSpace::ApplicationData
223 && self.last_ack_eliciting.is_none()
224 {
225 // For Initial and Handshake spaces, make sure that we have a PTO baseline
226 // always. See `LossRecoverySpace::pto_base_time()` for details.
227 self.last_ack_eliciting = Some(sent_packet.time_sent());
228 }
229 self.sent_packets.track(sent_packet);
230 }
231
232 /// If we are only sending ACK frames, send a PING frame after 2 PTOs so that
233 /// the peer sends an ACK frame. If we have received lots of packets and no ACK,
234 /// send a PING frame after 1 PTO. Note that this can't be within a PTO, or
235 /// we would risk setting up a feedback loop; having this many packets
236 /// outstanding can be normal and we don't want to PING too often.
237 #[must_use]
238 pub fn should_probe(&self, pto: Duration, now: Instant) -> bool {
239 let n_pto = if self.sent_packets.len() >= MAX_OUTSTANDING_UNACK {
240 1
241 } else if self.sent_packets.len() >= MIN_OUTSTANDING_UNACK {
242 2
243 } else {
244 return false;
245 };
246 self.last_ack_eliciting
247 .is_some_and(|t| now > t + (pto * n_pto))
248 }
249
250 fn remove_outstanding(&mut self, count: usize) {
251 debug_assert!(self.in_flight_outstanding >= count);
252 self.in_flight_outstanding -= count;
253 if self.in_flight_outstanding == 0 {
254 qtrace!("remove_packet outstanding == 0 for space {}", self.space);
255 }
256 }
257
258 fn remove_packet(&mut self, p: &SentPacket) {
259 if p.ack_eliciting() {
260 self.remove_outstanding(1);
261 }
262 }
263
264 /// Remove all newly acknowledged packets.
265 /// Returns all the acknowledged packets, with the largest packet number first.
266 /// ...and a boolean indicating if any of those packets were ack-eliciting.
267 /// This operates more efficiently because it assumes that the input is sorted
268 /// in the order that an ACK frame is (from the top).
269 fn remove_acked<R>(&mut self, acked_ranges: R, stats: &mut Stats) -> (Vec<SentPacket>, bool)
270 where
271 R: IntoIterator<Item = RangeInclusive<PacketNumber>>,
272 R::IntoIter: ExactSizeIterator,
273 {
274 let acked = self.sent_packets.take_ranges(acked_ranges);
275 let mut eliciting = false;
276 for p in &acked {
277 self.remove_packet(p);
278 eliciting |= p.ack_eliciting();
279 if p.lost() {
280 stats.late_ack += 1;
281 }
282 if p.pto_fired() {
283 stats.pto_ack += 1;
284 }
285 }
286 (acked, eliciting)
287 }
288
289 /// Remove all tracked packets from the space.
290 /// This is called by a client when 0-RTT packets are dropped, when a Retry is received
291 /// and when keys are dropped.
292 fn remove_ignored(&mut self) -> impl Iterator<Item = SentPacket> {
293 self.in_flight_outstanding = 0;
294 std::mem::take(&mut self.sent_packets).drain_all()
295 }
296
297 /// Remove the primary path marking on any packets this is tracking.
298 fn migrate(&mut self) {
299 for pkt in self.sent_packets.iter_mut() {
300 pkt.clear_primary_path();
301 }
302 }
303
304 /// Remove old packets that we've been tracking in case they get acknowledged.
305 /// We try to keep these around until a probe is sent for them, so it is
306 /// important that `cd` is set to at least the current PTO time; otherwise we
307 /// might remove all in-flight packets and stop sending probes.
308 fn remove_old_lost(&mut self, now: Instant, cd: Duration) {
309 let removed = self.sent_packets.remove_expired(now, cd);
310 self.remove_outstanding(removed);
311 }
312
313 /// Detect lost packets.
314 /// `loss_delay` is the time we will wait before declaring something lost.
315 /// `cleanup_delay` is the time we will wait before cleaning up a lost packet.
316 pub fn detect_lost_packets(
317 &mut self,
318 now: Instant,
319 loss_delay: Duration,
320 cleanup_delay: Duration,
321 lost_packets: &mut Vec<SentPacket>,
322 ) {
323 // Housekeeping.
324 self.remove_old_lost(now, cleanup_delay);
325
326 qtrace!(
327 "detect lost {}: now={now:?} delay={loss_delay:?}",
328 self.space,
329 );
330 self.first_ooo_time = None;
331
332 let largest_acked = self.largest_acked;
333
334 for packet in self
335 .sent_packets
336 .iter_mut()
337 // BTreeMap iterates in order of ascending PN
338 .take_while(|p| largest_acked.is_some_and(|largest_ack| p.pn() < largest_ack))
339 {
340 // Packets sent before now - loss_delay are deemed lost.
341 if packet.time_sent() + loss_delay <= now {
342 qtrace!(
343 "lost={}, time sent {:?} is before lost_delay {loss_delay:?}",
344 packet.pn(),
345 packet.time_sent()
346 );
347 } else if largest_acked >= Some(packet.pn() + PACKET_THRESHOLD) {
348 qtrace!(
349 "lost={}, is >= {PACKET_THRESHOLD} from largest acked {largest_acked:?}",
350 packet.pn()
351 );
352 } else {
353 if largest_acked.is_some() {
354 self.first_ooo_time = Some(packet.time_sent());
355 }
356 // No more packets can be declared lost after this one.
357 break;
358 }
359
360 if packet.declare_lost(now) {
361 lost_packets.push(packet.clone());
362 }
363 }
364 }
365 }
366
367 #[derive(Debug)]
368 pub struct LossRecoverySpaces {
369 spaces: EnumMap<PacketNumberSpace, Option<LossRecoverySpace>>,
370 }
371
372 impl LossRecoverySpaces {
373 /// Drop a packet number space and return all the packets that were
374 /// outstanding, so that those can be marked as lost.
375 ///
376 /// # Panics
377 ///
378 /// If the space has already been removed.
379 pub fn drop_space(&mut self, space: PacketNumberSpace) -> impl IntoIterator<Item = SentPacket> {
380 let sp = self.spaces[space].take();
381 assert_ne!(
382 space,
383 PacketNumberSpace::ApplicationData,
384 "discarding application space"
385 );
386 sp.expect("has not been removed").remove_ignored()
387 }
388
389 #[must_use]
390 pub fn get(&self, space: PacketNumberSpace) -> Option<&LossRecoverySpace> {
391 self.spaces[space].as_ref()
392 }
393
394 pub fn get_mut(&mut self, space: PacketNumberSpace) -> Option<&mut LossRecoverySpace> {
395 self.spaces[space].as_mut()
396 }
397
398 fn iter(&self) -> impl Iterator<Item = &LossRecoverySpace> {
399 self.spaces.iter().filter_map(|(_, recvd)| recvd.as_ref())
400 }
401
402 fn iter_mut(&mut self) -> impl Iterator<Item = &mut LossRecoverySpace> {
403 self.spaces
404 .iter_mut()
405 .filter_map(|(_, recvd)| recvd.as_mut())
406 }
407 }
408
409 impl Default for LossRecoverySpaces {
410 fn default() -> Self {
411 Self {
412 spaces: EnumMap::from_array([
413 Some(LossRecoverySpace::new(PacketNumberSpace::Initial)),
414 Some(LossRecoverySpace::new(PacketNumberSpace::Handshake)),
415 Some(LossRecoverySpace::new(PacketNumberSpace::ApplicationData)),
416 ]),
417 }
418 }
419 }
420
421 #[derive(Debug)]
422 struct PtoState {
423 /// The packet number space that caused the PTO to fire.
424 space: PacketNumberSpace,
425 /// The number of probes that we have sent.
426 count: usize,
427 packets: usize,
428 /// The complete set of packet number spaces that can have probes sent.
429 probe: PacketNumberSpaceSet,
430 }
431
432 impl PtoState {
433 /// The number of packets we send on a PTO.
434 fn pto_packet_count(space: PacketNumberSpace) -> usize {
435 if space == PacketNumberSpace::ApplicationData {
436 MAX_PTO_PACKET_COUNT
437 } else {
438 // For the Initial and Handshake spaces, we only send one packet on PTO. This avoids
439 // sending useless PING-only packets when only a single packet was lost, which is the
440 // common case. These PINGs use cwnd and amplification window space, and sending them
441 // hence makes the handshake more brittle.
442 1
443 }
444 }
445
446 pub fn new(space: PacketNumberSpace, probe: PacketNumberSpaceSet) -> Self {
447 debug_assert!(probe.contains(space));
448 Self {
449 space,
450 count: 1,
451 packets: Self::pto_packet_count(space),
452 probe,
453 }
454 }
455
456 pub fn pto(&mut self, space: PacketNumberSpace, probe: PacketNumberSpaceSet) {
457 debug_assert!(probe.contains(space));
458 self.space = space;
459 self.count += 1;
460 self.packets = Self::pto_packet_count(space);
461 self.probe = probe;
462 }
463
464 pub const fn count(&self) -> usize {
465 self.count
466 }
467
468 pub fn count_pto(&self, stats: &mut Stats) {
469 stats.add_pto_count(self.count);
470 }
471
472 /// Generate a sending profile, indicating what space it should be from.
473 /// This takes a packet from the supply if one remains, or returns `None`.
474 pub fn send_profile(&mut self, mtu: usize) -> Option<SendProfile> {
475 (self.packets > 0).then(|| {
476 // This is a PTO, so ignore the limit.
477 self.packets -= 1;
478 SendProfile::new_pto(self.space, mtu, self.probe)
479 })
480 }
481 }
482
483 #[derive(Debug)]
484 pub struct LossRecovery {
485 /// When the handshake was confirmed, if it has been.
486 confirmed_time: Option<Instant>,
487 pto_state: Option<PtoState>,
488 spaces: LossRecoverySpaces,
489 qlog: NeqoQlog,
490 stats: StatsCell,
491 /// The factor by which the PTO period is reduced.
492 /// This enables faster probing at a cost in additional lost packets.
493 fast_pto: u8,
494 }
495
496 impl LossRecovery {
497 #[must_use]
498 pub fn new(stats: StatsCell, fast_pto: u8) -> Self {
499 Self {
500 confirmed_time: None,
501 pto_state: None,
502 spaces: LossRecoverySpaces::default(),
503 qlog: NeqoQlog::default(),
504 stats,
505 fast_pto,
506 }
507 }
508
509 #[must_use]
510 pub fn largest_acknowledged_pn(&self, pn_space: PacketNumberSpace) -> Option<PacketNumber> {
511 self.spaces.get(pn_space)?.largest_acked
512 }
513
514 pub fn set_qlog(&mut self, qlog: NeqoQlog) {
515 self.qlog = qlog;
516 }
517
518 /// Drop all 0rtt packets.
519 pub fn drop_0rtt(&mut self, primary_path: &PathRef, now: Instant) -> Vec<SentPacket> {
520 let Some(sp) = self.spaces.get_mut(PacketNumberSpace::ApplicationData) else {
521 return Vec::new();
522 };
523 if sp.largest_acked.is_some() {
524 qwarn!("0-RTT packets already acknowledged, not dropping");
525 return Vec::new();
526 }
527 let mut dropped = sp.remove_ignored().collect::<Vec<_>>();
528 let mut path = primary_path.borrow_mut();
529 for p in &mut dropped {
530 path.discard_packet(p, now, &mut self.stats.borrow_mut());
531 }
532 dropped
533 }
534
535 pub fn on_packet_sent(&mut self, path: &PathRef, mut sent_packet: SentPacket, now: Instant) {
536 let pn_space = PacketNumberSpace::from(sent_packet.packet_type());
537 qtrace!("[{self}] packet {pn_space}-{} sent", sent_packet.pn());
538 if let Some(space) = self.spaces.get_mut(pn_space) {
539 path.borrow_mut().packet_sent(&mut sent_packet, now);
540 space.on_packet_sent(sent_packet);
541 } else {
542 qwarn!(
543 "[{self}] ignoring {pn_space}-{} from dropped space",
544 sent_packet.pn()
545 );
546 }
547 }
548
549 /// Whether to probe the path.
550 #[must_use]
551 pub fn should_probe(&self, pto: Duration, now: Instant) -> bool {
552 self.spaces
553 .get(PacketNumberSpace::ApplicationData)
554 .is_some_and(|sp| sp.should_probe(pto, now))
555 }
556
557 /// Record an RTT sample.
558 fn rtt_sample(
559 &self,
560 rtt: &mut RttEstimate,
561 send_time: Instant,
562 now: Instant,
563 ack_delay: Duration,
564 ) {
565 let source = if self.confirmed_time.is_some_and(|t| t < send_time) {
566 RttSource::AckConfirmed
567 } else {
568 RttSource::Ack
569 };
570 if let Some(sample) = now.checked_duration_since(send_time) {
571 rtt.update(&self.qlog, sample, ack_delay, source, now);
572 }
573 }
574
575 const fn confirmed(&self) -> bool {
576 self.confirmed_time.is_some()
577 }
578
579 /// Returns (acked packets, lost packets)
580 pub fn on_ack_received<R>(
581 &mut self,
582 primary_path: &PathRef,
583 pn_space: PacketNumberSpace,
584 acked_ranges: R,
585 ack_ecn: Option<ecn::Count>,
586 ack_delay: Duration,
587 now: Instant,
588 ) -> (Vec<SentPacket>, Vec<SentPacket>)
589 where
590 R: IntoIterator<Item = RangeInclusive<PacketNumber>>,
591 R::IntoIter: ExactSizeIterator,
592 {
593 let Some(space) = self.spaces.get_mut(pn_space) else {
594 qinfo!("ACK on discarded space");
595 return (Vec::new(), Vec::new());
596 };
597
598 let (acked_packets, any_ack_eliciting) =
599 space.remove_acked(acked_ranges, &mut self.stats.borrow_mut());
600 let Some(largest_acked_pkt) = acked_packets.first() else {
601 // No new information.
602 return (Vec::new(), Vec::new());
603 };
604
605 // Track largest PN acked per space
606 let prev_largest_acked = space.largest_acked_sent_time;
607 if Some(largest_acked_pkt.pn()) > space.largest_acked {
608 space.largest_acked = Some(largest_acked_pkt.pn());
609
610 // If the largest acknowledged is newly acked and any newly acked
611 // packet was ack-eliciting, update the RTT. (-recovery 5.1)
612 space.largest_acked_sent_time = Some(largest_acked_pkt.time_sent());
613 if any_ack_eliciting && largest_acked_pkt.on_primary_path() {
614 self.rtt_sample(
615 primary_path.borrow_mut().rtt_mut(),
616 largest_acked_pkt.time_sent(),
617 now,
618 ack_delay,
619 );
620 }
621 }
622
623 qdebug!(
624 "[{self}] ACK for {pn_space:?} - largest_acked={}",
625 largest_acked_pkt.pn()
626 );
627
628 // Perform loss detection.
629 // PTO is used to remove lost packets from in-flight accounting.
630 // We need to ensure that we have sent any PTO probes before they are removed
631 // as we rely on the count of in-flight packets to determine whether to send
632 // another probe. Removing them too soon would result in not sending on PTO.
633 let cleanup_delay = self.pto_period(primary_path.borrow().rtt());
634 let Some(sp) = self.spaces.get_mut(pn_space) else {
635 return (Vec::new(), Vec::new());
636 };
637 let loss_delay = primary_path.borrow().rtt().loss_delay();
638 let mut lost = Vec::new();
639 sp.detect_lost_packets(now, loss_delay, cleanup_delay, &mut lost);
640 self.stats.borrow_mut().lost += lost.len();
641
642 // Tell the congestion controller about any lost packets.
643 // The PTO for congestion control is the raw number, without exponential
644 // backoff, so that we can determine persistent congestion.
645 primary_path.borrow_mut().on_packets_lost(
646 prev_largest_acked,
647 self.confirmed(),
648 &lost,
649 &mut self.stats.borrow_mut(),
650 now,
651 );
652
653 // This must happen after on_packets_lost. If in recovery, this could
654 // take us out, and then lost packets will start a new recovery period
655 // when it shouldn't.
656 primary_path.borrow_mut().on_packets_acked(
657 &acked_packets,
658 ack_ecn,
659 now,
660 &mut self.stats.borrow_mut(),
661 );
662
663 self.pto_state = None;
664
665 (acked_packets, lost)
666 }
667
668 /// When receiving a retry, get all the sent packets so that they can be flushed.
669 /// We also need to pretend that they never happened for the purposes of congestion control.
670 pub fn retry(&mut self, primary_path: &PathRef, now: Instant) -> Vec<SentPacket> {
671 self.pto_state = None;
672 let mut dropped = self
673 .spaces
674 .iter_mut()
675 .flat_map(LossRecoverySpace::remove_ignored)
676 .collect::<Vec<_>>();
677 let mut path = primary_path.borrow_mut();
678 for p in &mut dropped {
679 path.discard_packet(p, now, &mut self.stats.borrow_mut());
680 }
681 dropped
682 }
683
684 fn confirm(&mut self, rtt: &RttEstimate, now: Instant) {
685 debug_assert!(self.confirmed_time.is_none());
686 self.confirmed_time = Some(now);
687 // Up until now, the ApplicationData space has been ignored for PTO.
688 // So maybe fire a PTO.
689 if let Some(pto) = self.pto_time(rtt, PacketNumberSpace::ApplicationData) {
690 if pto < now {
691 let probes = enum_set!(PacketNumberSpace::ApplicationData);
692 self.fire_pto(PacketNumberSpace::ApplicationData, probes, now);
693 }
694 }
695 }
696
697 /// This function is called when the connection migrates.
698 /// It marks all packets that are outstanding as having being sent on a non-primary path.
699 /// This way failure to deliver on the old path doesn't count against the congestion
700 /// control state on the new path and the RTT measurements don't apply either.
701 pub fn migrate(&mut self) {
702 for space in self.spaces.iter_mut() {
703 space.migrate();
704 }
705 }
706
707 /// Discard state for a given packet number space.
708 pub fn discard(&mut self, primary_path: &PathRef, space: PacketNumberSpace, now: Instant) {
709 qdebug!("[{self}] Reset loss recovery state for {space:?}");
710 let mut path = primary_path.borrow_mut();
711 for p in self.spaces.drop_space(space) {
712 path.discard_packet(&p, now, &mut self.stats.borrow_mut());
713 }
714
715 // We just made progress, so discard PTO count.
716 // The spec says that clients should not do this until confirming that
717 // the server has completed address validation, but ignore that.
718 self.pto_state = None;
719
720 if space == PacketNumberSpace::Handshake {
721 self.confirm(path.rtt(), now);
722 }
723 }
724
725 /// Calculate when the next timeout is likely to be. This is the earlier of the loss timer
726 /// and the PTO timer; either or both might be disabled, so this can return `None`.
727 #[must_use]
728 pub fn next_timeout(&self, path: &Path) -> Option<Instant> {
729 let rtt = path.rtt();
730 let loss_time = self.earliest_loss_time(rtt);
731 let pto_time = if path.pto_possible() {
732 self.earliest_pto(rtt)
733 } else {
734 None
735 };
736 qtrace!("[{self}] next_timeout loss={loss_time:?} pto={pto_time:?}");
737 match (loss_time, pto_time) {
738 (Some(loss_time), Some(pto_time)) => Some(min(loss_time, pto_time)),
739 (Some(loss_time), None) => Some(loss_time),
740 (None, Some(pto_time)) => Some(pto_time),
741 (None, None) => None,
742 }
743 }
744
745 /// Find when the earliest sent packet should be considered lost.
746 fn earliest_loss_time(&self, rtt: &RttEstimate) -> Option<Instant> {
747 self.spaces
748 .iter()
749 .filter_map(LossRecoverySpace::loss_recovery_timer_start)
750 .min()
751 .map(|val| val + rtt.loss_delay())
752 }
753
754 /// Simple wrapper for the PTO calculation that avoids borrow check rules.
755 fn pto_period_inner(
756 rtt: &RttEstimate,
757 pto_state: Option<&PtoState>,
758 confirmed: bool,
759 fast_pto: u8,
760 ) -> Duration {
761 // This is a complicated (but safe) way of calculating:
762 // base_pto * F * 2^pto_count
763 // where F = fast_pto / FAST_PTO_SCALE (== 1 by default)
764 let pto_count = pto_state.map_or(0, |p| u32::try_from(p.count).unwrap_or(0));
765 rtt.pto(confirmed)
766 .checked_mul(u32::from(fast_pto) << min(pto_count, u32::BITS - u8::BITS))
767 .map_or(Duration::from_secs(3600), |p| p / u32::from(FAST_PTO_SCALE))
768 }
769
770 /// Get the current PTO period for the given packet number space.
771 /// Unlike calling `RttEstimate::pto` directly, this includes exponential backoff.
772 fn pto_period(&self, rtt: &RttEstimate) -> Duration {
773 Self::pto_period_inner(
774 rtt,
775 self.pto_state.as_ref(),
776 self.confirmed(),
777 self.fast_pto,
778 )
779 }
780
781 // Calculate PTO time for the given space.
782 fn pto_time(&self, rtt: &RttEstimate, pn_space: PacketNumberSpace) -> Option<Instant> {
783 self.spaces
784 .get(pn_space)?
785 .pto_base_time()
786 .map(|t| t + self.pto_period(rtt))
787 }
788
789 /// Find the earliest PTO time for all active packet number spaces.
790 /// Ignore Application if either Initial or Handshake have an active PTO.
791 fn earliest_pto(&self, rtt: &RttEstimate) -> Option<Instant> {
792 if self.confirmed() {
793 self.pto_time(rtt, PacketNumberSpace::ApplicationData)
794 } else {
795 self.pto_time(rtt, PacketNumberSpace::Initial)
796 .iter()
797 .chain(self.pto_time(rtt, PacketNumberSpace::Handshake).iter())
798 .min()
799 .copied()
800 }
801 }
802
803 fn fire_pto(
804 &mut self,
805 pn_space: PacketNumberSpace,
806 allow_probes: PacketNumberSpaceSet,
807 now: Instant,
808 ) {
809 if let Some(st) = &mut self.pto_state {
810 st.pto(pn_space, allow_probes);
811 } else {
812 self.pto_state = Some(PtoState::new(pn_space, allow_probes));
813 }
814
815 if let Some(st) = &mut self.pto_state {
816 st.count_pto(&mut self.stats.borrow_mut());
817 qlog::metrics_updated(&self.qlog, &[QlogMetric::PtoCount(st.count())], now);
818 }
819 }
820
821 /// This checks whether the PTO timer has fired and fires it if needed.
822 /// When it has, mark packets as "lost" for the purposes of having frames
823 /// regenerated in subsequent packets. The packets aren't truly lost, so
824 /// we have to clone the `SentPacket` instance.
825 fn maybe_fire_pto(&mut self, primary_path: &PathRef, now: Instant, lost: &mut Vec<SentPacket>) {
826 let mut pto_space = None;
827 // The spaces in which we will allow probing.
828 let mut allow_probes = PacketNumberSpaceSet::default();
829 for pn_space in PacketNumberSpace::iter() {
830 let Some(t) = self.pto_time(primary_path.borrow().rtt(), pn_space) else {
831 continue;
832 };
833 allow_probes.insert(pn_space);
834 if t > now {
835 continue;
836 }
837 qdebug!("[{self}] PTO timer fired for {pn_space:?}");
838 let Some(space) = self.spaces.get_mut(pn_space) else {
839 continue;
840 };
841 let mut size = 0;
842 let mtu = primary_path.borrow().plpmtu();
843 lost.extend(
844 space
845 .pto_packets()
846 // Do not consider all packets for retransmission on PTO. On
847 // a high bandwidth delay connection, that would be a lot of
848 // `SentPacket`s to clone.
849 //
850 // Given that we are sending at most `MAX_PTO_PACKET_COUNT`
851 // packets on PTO, consider as many packets for
852 // retransmission as would fit into those PTO packets.
853 .take_while(move |p| {
854 size += p.len();
855 size <= MAX_PTO_PACKET_COUNT * mtu
856 })
857 .cloned(),
858 );
859 pto_space = pto_space.or(Some(pn_space));
860 }
861
862 // This has to happen outside the loop. Increasing the PTO count here causes the
863 // pto_time to increase which might cause PTO for later packet number spaces to not fire.
864 if let Some(pn_space) = pto_space {
865 qtrace!("[{self}] PTO {pn_space}, probing {allow_probes:?}");
866 self.fire_pto(pn_space, allow_probes, now);
867 }
868 }
869
870 pub fn timeout(&mut self, primary_path: &PathRef, now: Instant) -> Vec<SentPacket> {
871 qtrace!("[{self}] timeout {now:?}");
872
873 let loss_delay = primary_path.borrow().rtt().loss_delay();
874 let confirmed = self.confirmed();
875
876 let mut lost_packets = Vec::new();
877 for space in self.spaces.iter_mut() {
878 let first = lost_packets.len(); // The first packet lost in this space.
879 let pto = Self::pto_period_inner(
880 primary_path.borrow().rtt(),
881 self.pto_state.as_ref(),
882 confirmed,
883 self.fast_pto,
884 );
885 space.detect_lost_packets(now, loss_delay, pto, &mut lost_packets);
886
887 primary_path.borrow_mut().on_packets_lost(
888 space.largest_acked_sent_time,
889 confirmed,
890 &lost_packets[first..],
891 &mut self.stats.borrow_mut(),
892 now,
893 );
894 }
895 self.stats.borrow_mut().lost += lost_packets.len();
896
897 self.maybe_fire_pto(primary_path, now, &mut lost_packets);
898 lost_packets
899 }
900
901 /// Check how packets should be sent, based on whether there is a PTO,
902 /// what the current congestion window is, and what the pacer says.
903 #[expect(clippy::option_if_let_else, reason = "Alternative is less readable.")]
904 pub fn send_profile(&mut self, path: &Path, now: Instant) -> SendProfile {
905 qtrace!("[{self}] get send profile {now:?}");
906 let sender = path.sender();
907 let mtu = path.plpmtu();
908 #[allow(
909 clippy::allow_attributes,
910 clippy::return_and_then,
911 reason = "TODO: False positive on nightly; function isn't returning Option or Result"
912 )]
913 if let Some(profile) = self
914 .pto_state
915 .as_mut()
916 .and_then(|pto| pto.send_profile(mtu))
917 {
918 profile
919 } else {
920 let limit = min(sender.cwnd_avail(), path.amplification_limit());
921 if limit > mtu {
922 // More than an MTU available; we might need to pace.
923 if sender
924 .next_paced(path.rtt().estimate())
925 .is_some_and(|t| t > now)
926 {
927 SendProfile::new_paced()
928 } else {
929 SendProfile::new_limited(mtu)
930 }
931 } else if sender.recovery_packet() {
932 // After entering recovery, allow a packet to be sent immediately.
933 // This uses the PTO machinery, probing in all spaces. This will
934 // result in a PING being sent in every active space.
935 SendProfile::new_pto(PacketNumberSpace::Initial, mtu, PacketNumberSpaceSet::all())
936 } else {
937 SendProfile::new_limited(limit)
938 }
939 }
940 }
941 }
942
943 impl Display for LossRecovery {
944 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
945 write!(f, "LossRecovery")
946 }
947 }
948
949 #[cfg(test)]
950 mod tests {
951 use std::{
952 cell::RefCell,
953 ops::{Deref, DerefMut, RangeInclusive},
954 rc::Rc,
955 time::{Duration, Instant},
956 };
957
958 use neqo_common::qlog::NeqoQlog;
959 use test_fixture::{now, DEFAULT_ADDR};
960
961 use super::{
962 LossRecovery, LossRecoverySpace, PacketNumberSpace, SendProfile, SentPacket, FAST_PTO_SCALE,
963 };
964 use crate::{
965 cid::{ConnectionId, ConnectionIdEntry},
966 ecn,
967 packet::{PacketNumber, PacketType},
968 path::{Path, PathRef},
969 stats::{Stats, StatsCell},
970 ConnectionParameters,
971 };
972
973 // Shorthand for a time in milliseconds.
974 const fn ms(t: u64) -> Duration {
975 Duration::from_millis(t)
976 }
977
978 const ON_SENT_SIZE: usize = 100;
979 /// An initial RTT for using with `setup_lr`.
980 const TEST_RTT: Duration = ms(7000);
981 const TEST_RTTVAR: Duration = ms(3500);
982
983 struct Fixture {
984 lr: LossRecovery,
985 path: PathRef,
986 }
987
988 // This shadows functions on the base object so that the path and RTT estimator
989 // is used consistently in the tests. It also simplifies the function signatures.
990 impl Fixture {
991 pub fn on_ack_received(
992 &mut self,
993 pn_space: PacketNumberSpace,
994 acked_ranges: Vec<RangeInclusive<PacketNumber>>,
995 ack_ecn: Option<ecn::Count>,
996 ack_delay: Duration,
997 now: Instant,
998 ) -> (Vec<SentPacket>, Vec<SentPacket>) {
999 self.lr
1000 .on_ack_received(&self.path, pn_space, acked_ranges, ack_ecn, ack_delay, now)
1001 }
1002
1003 pub fn on_packet_sent(&mut self, sent_packet: SentPacket, now: Instant) {
1004 self.lr.on_packet_sent(&self.path, sent_packet, now);
1005 }
1006
1007 pub fn timeout(&mut self, now: Instant) -> Vec<SentPacket> {
1008 self.lr.timeout(&self.path, now)
1009 }
1010
1011 pub fn next_timeout(&self) -> Option<Instant> {
1012 self.lr.next_timeout(&self.path.borrow())
1013 }
1014
1015 pub fn discard(&mut self, space: PacketNumberSpace, now: Instant) {
1016 self.lr.discard(&self.path, space, now);
1017 }
1018
1019 pub fn pto_time(&self, space: PacketNumberSpace) -> Option<Instant> {
1020 self.lr.pto_time(self.path.borrow().rtt(), space)
1021 }
1022
1023 pub fn send_profile(&mut self, now: Instant) -> SendProfile {
1024 self.lr.send_profile(&self.path.borrow(), now)
1025 }
1026 }
1027
1028 impl Default for Fixture {
1029 fn default() -> Self {
1030 let stats = StatsCell::default();
1031 let mut path = Path::temporary(
1032 DEFAULT_ADDR,
1033 DEFAULT_ADDR,
1034 &ConnectionParameters::default(),
1035 NeqoQlog::default(),
1036 now(),
1037 &mut stats.borrow_mut(),
1038 );
1039 path.make_permanent(
1040 None,
1041 ConnectionIdEntry::new(0, ConnectionId::from(&[1, 2, 3]), [0; 16]),
1042 );
1043 path.set_primary(true, now());
1044 path.rtt_mut().set_initial(TEST_RTT);
1045 Self {
1046 lr: LossRecovery::new(stats, FAST_PTO_SCALE),
1047 path: Rc::new(RefCell::new(path)),
1048 }
1049 }
1050 }
1051
1052 // Most uses of the fixture only care about the loss recovery piece,
1053 // but the internal functions need the other bits.
1054 impl Deref for Fixture {
1055 type Target = LossRecovery;
1056 fn deref(&self) -> &Self::Target {
1057 &self.lr
1058 }
1059 }
1060
1061 impl DerefMut for Fixture {
1062 fn deref_mut(&mut self) -> &mut Self::Target {
1063 &mut self.lr
1064 }
1065 }
1066
1067 fn assert_rtts(
1068 lr: &Fixture,
1069 latest_rtt: Duration,
1070 smoothed_rtt: Duration,
1071 rttvar: Duration,
1072 min_rtt: Duration,
1073 ) {
1074 let p = lr.path.borrow();
1075 let rtt = p.rtt();
1076 println!(
1077 "rtts: {:?} {:?} {:?} {:?}",
1078 rtt.latest(),
1079 rtt.estimate(),
1080 rtt.rttvar(),
1081 rtt.minimum(),
1082 );
1083 assert_eq!(rtt.latest(), latest_rtt, "latest RTT");
1084 assert_eq!(rtt.estimate(), smoothed_rtt, "smoothed RTT");
1085 assert_eq!(rtt.rttvar(), rttvar, "RTT variance");
1086 assert_eq!(rtt.minimum(), min_rtt, "min RTT");
1087 }
1088
1089 fn assert_sent_times(
1090 lr: &Fixture,
1091 initial: Option<Instant>,
1092 handshake: Option<Instant>,
1093 app_data: Option<Instant>,
1094 ) {
1095 let est = |sp| {
1096 lr.spaces
1097 .get(sp)
1098 .and_then(LossRecoverySpace::loss_recovery_timer_start)
1099 };
1100 println!(
1101 "loss times: {:?} {:?} {:?}",
1102 est(PacketNumberSpace::Initial),
1103 est(PacketNumberSpace::Handshake),
1104 est(PacketNumberSpace::ApplicationData),
1105 );
1106 assert_eq!(
1107 est(PacketNumberSpace::Initial),
1108 initial,
1109 "Initial earliest sent time"
1110 );
1111 assert_eq!(
1112 est(PacketNumberSpace::Handshake),
1113 handshake,
1114 "Handshake earliest sent time"
1115 );
1116 assert_eq!(
1117 est(PacketNumberSpace::ApplicationData),
1118 app_data,
1119 "AppData earliest sent time"
1120 );
1121 }
1122
1123 fn assert_no_sent_times(lr: &Fixture) {
1124 assert_sent_times(lr, None, None, None);
1125 }
1126
1127 // In most of the tests below, packets are sent at a fixed cadence, with PACING between each.
1128 const PACING: Duration = ms(7);
1129 fn pn_time(pn: u64) -> Instant {
1130 now() + (PACING * pn.try_into().unwrap())
1131 }
1132
1133 fn pace(lr: &mut Fixture, count: u64) {
1134 for pn in 0..count {
1135 lr.on_packet_sent(
1136 SentPacket::new(
1137 PacketType::Short,
1138 pn,
1139 pn_time(pn),
1140 true,
1141 Vec::new(),
1142 ON_SENT_SIZE,
1143 ),
1144 Instant::now(),
1145 );
1146 }
1147 }
1148
1149 const ACK_DELAY: Duration = ms(24);
1150 /// Acknowledge PN with the identified delay.
1151 fn ack(lr: &mut Fixture, pn: u64, delay: Duration) {
1152 lr.on_ack_received(
1153 PacketNumberSpace::ApplicationData,
1154 vec![pn..=pn],
1155 None,
1156 ACK_DELAY,
1157 pn_time(pn) + delay,
1158 );
1159 }
1160
1161 fn add_sent(lrs: &mut LossRecoverySpace, max_pn: PacketNumber) {
1162 for pn in 0..=max_pn {
1163 lrs.on_packet_sent(SentPacket::new(
1164 PacketType::Short,
1165 pn,
1166 pn_time(pn),
1167 true,
1168 Vec::new(),
1169 ON_SENT_SIZE,
1170 ));
1171 }
1172 }
1173
1174 fn match_acked(acked: &[SentPacket], expected: &[PacketNumber]) {
1175 assert_eq!(
1176 acked.iter().map(SentPacket::pn).collect::<Vec<_>>(),
1177 expected
1178 );
1179 }
1180
1181 #[test]
1182 fn remove_acked() {
1183 let mut lrs = LossRecoverySpace::new(PacketNumberSpace::ApplicationData);
1184 let mut stats = Stats::default();
1185 add_sent(&mut lrs, 10);
1186 let (acked, _) = lrs.remove_acked(vec![], &mut stats);
1187 assert!(acked.is_empty());
1188 let (acked, _) = lrs.remove_acked(vec![7..=8, 2..=4], &mut stats);
1189 match_acked(&acked, &[8, 7, 4, 3, 2]);
1190 let (acked, _) = lrs.remove_acked(vec![8..=11], &mut stats);
1191 match_acked(&acked, &[10, 9]);
1192 let (acked, _) = lrs.remove_acked(vec![0..=2], &mut stats);
1193 match_acked(&acked, &[1, 0]);
1194 let (acked, _) = lrs.remove_acked(vec![5..=6], &mut stats);
1195 match_acked(&acked, &[6, 5]);
1196 }
1197
1198 #[test]
1199 fn initial_rtt() {
1200 let mut lr = Fixture::default();
1201 pace(&mut lr, 1);
1202 let rtt = ms(100);
1203 ack(&mut lr, 0, rtt);
1204 assert_rtts(&lr, rtt, rtt, rtt / 2, rtt);
1205 assert_no_sent_times(&lr);
1206 }
1207
1208 /// Send `n` packets (using PACING), then acknowledge the first.
1209 fn setup_lr(n: u64) -> Fixture {
1210 let mut lr = Fixture::default();
1211 pace(&mut lr, n);
1212 ack(&mut lr, 0, TEST_RTT);
1213 assert_rtts(&lr, TEST_RTT, TEST_RTT, TEST_RTTVAR, TEST_RTT);
1214 assert_no_sent_times(&lr);
1215 lr
1216 }
1217
1218 // The ack delay is removed from any RTT estimate.
1219 #[test]
1220 fn ack_delay_adjusted() {
1221 let mut lr = setup_lr(2);
1222 ack(&mut lr, 1, TEST_RTT + ACK_DELAY);
1223 // RTT stays the same, but the RTTVAR is adjusted downwards.
1224 assert_rtts(&lr, TEST_RTT, TEST_RTT, TEST_RTTVAR * 3 / 4, TEST_RTT);
1225 assert_no_sent_times(&lr);
1226 }
1227
1228 // The ack delay is ignored when it would cause a sample to be less than min_rtt.
1229 #[test]
1230 fn ack_delay_ignored() {
1231 let mut lr = setup_lr(2);
1232 let extra = ms(8);
1233 assert!(extra < ACK_DELAY);
1234 ack(&mut lr, 1, TEST_RTT + extra);
1235 let expected_rtt = TEST_RTT + (extra / 8);
1236 let expected_rttvar = (TEST_RTTVAR * 3 + extra) / 4;
1237 assert_rtts(
1238 &lr,
1239 TEST_RTT + extra,
1240 expected_rtt,
1241 expected_rttvar,
1242 TEST_RTT,
1243 );
1244 assert_no_sent_times(&lr);
1245 }
1246
1247 // A lower observed RTT is used as min_rtt (and ack delay is ignored).
1248 #[test]
1249 fn reduce_min_rtt() {
1250 let mut lr = setup_lr(2);
1251 let delta = ms(4);
1252 let reduced_rtt = TEST_RTT - delta;
1253 ack(&mut lr, 1, reduced_rtt);
1254 let expected_rtt = TEST_RTT - (delta / 8);
1255 let expected_rttvar = (TEST_RTTVAR * 3 + delta) / 4;
1256 assert_rtts(&lr, reduced_rtt, expected_rtt, expected_rttvar, reduced_rtt);
1257 assert_no_sent_times(&lr);
1258 }
1259
1260 // Acknowledging something again has no effect.
1261 #[test]
1262 fn no_new_acks() {
1263 let mut lr = setup_lr(1);
1264 let check = |lr: &Fixture| {
1265 assert_rtts(lr, TEST_RTT, TEST_RTT, TEST_RTTVAR, TEST_RTT);
1266 assert_no_sent_times(lr);
1267 };
1268 check(&lr);
1269
1270 ack(&mut lr, 0, ms(1339)); // much delayed ACK
1271 check(&lr);
1272
1273 ack(&mut lr, 0, ms(3)); // time travel!
1274 check(&lr);
1275 }
1276
1277 // Test time loss detection as part of handling a regular ACK.
1278 #[test]
1279 fn time_loss_detection_gap() {
1280 let mut lr = Fixture::default();
1281 // Create a single packet gap, and have pn 0 time out.
1282 // This can't use the default pacing, which is too tight.
1283 // So send two packets with 1/4 RTT between them. Acknowledge pn 1 after 1 RTT.
1284 // pn 0 should then be marked lost because it is then outstanding for 5RTT/4
1285 // the loss time for packets is 9RTT/8.
1286 lr.on_packet_sent(
1287 SentPacket::new(
1288 PacketType::Short,
1289 0,
1290 pn_time(0),
1291 true,
1292 Vec::new(),
1293 ON_SENT_SIZE,
1294 ),
1295 Instant::now(),
1296 );
1297 lr.on_packet_sent(
1298 SentPacket::new(
1299 PacketType::Short,
1300 1,
1301 pn_time(0) + TEST_RTT / 4,
1302 true,
1303 Vec::new(),
1304 ON_SENT_SIZE,
1305 ),
1306 Instant::now(),
1307 );
1308 let (_, lost) = lr.on_ack_received(
1309 PacketNumberSpace::ApplicationData,
1310 vec![1..=1],
1311 None,
1312 ACK_DELAY,
1313 pn_time(0) + (TEST_RTT * 5 / 4),
1314 );
1315 assert_eq!(lost.len(), 1);
1316 assert_no_sent_times(&lr);
1317 }
1318
1319 // Test time loss detection as part of an explicit timeout.
1320 #[test]
1321 fn time_loss_detection_timeout() {
1322 let mut lr = setup_lr(3);
1323
1324 // We want to declare PN 2 as acknowledged before we declare PN 1 as lost.
1325 // For this to work, we need PACING above to be less than 1/8 of an RTT.
1326 let pn1_sent_time = pn_time(1);
1327 let pn1_loss_time = pn1_sent_time + (TEST_RTT * 9 / 8);
1328 let pn2_ack_time = pn_time(2) + TEST_RTT;
1329 assert!(pn1_loss_time > pn2_ack_time);
1330
1331 let (_, lost) = lr.on_ack_received(
1332 PacketNumberSpace::ApplicationData,
1333 vec![2..=2],
1334 None,
1335 ACK_DELAY,
1336 pn2_ack_time,
1337 );
1338 assert!(lost.is_empty());
1339 // Run the timeout function here to force time-based loss recovery to be enabled.
1340 let lost = lr.timeout(pn2_ack_time);
1341 assert!(lost.is_empty());
1342 assert_sent_times(&lr, None, None, Some(pn1_sent_time));
1343
1344 // After time elapses, pn 1 is marked lost.
1345 let callback_time = lr.next_timeout();
1346 assert_eq!(callback_time, Some(pn1_loss_time));
1347 let packets = lr.timeout(pn1_loss_time);
1348 assert_eq!(packets.len(), 1);
1349 // Checking for expiration with zero delay lets us check the loss time.
1350 assert!(packets[0].expired(pn1_loss_time, Duration::new(0, 0)));
1351 assert_no_sent_times(&lr);
1352 }
1353
1354 #[test]
1355 fn big_gap_loss() {
1356 let mut lr = setup_lr(5); // This sends packets 0-4 and acknowledges pn 0.
1357
1358 // Acknowledge just 2-4, which will cause pn 1 to be marked as lost.
1359 assert_eq!(super::PACKET_THRESHOLD, 3);
1360 let (_, lost) = lr.on_ack_received(
1361 PacketNumberSpace::ApplicationData,
1362 vec![2..=4],
1363 None,
1364 ACK_DELAY,
1365 pn_time(4),
1366 );
1367 assert_eq!(lost.len(), 1);
1368 }
1369
1370 #[test]
1371 #[should_panic(expected = "discarding application space")]
1372 fn drop_app() {
1373 let mut lr = Fixture::default();
1374 lr.discard(PacketNumberSpace::ApplicationData, now());
1375 }
1376
1377 #[test]
1378 fn ack_after_drop() {
1379 let mut lr = Fixture::default();
1380 lr.discard(PacketNumberSpace::Initial, now());
1381 let (acked, lost) = lr.on_ack_received(
1382 PacketNumberSpace::Initial,
1383 vec![],
1384 None,
1385 Duration::from_millis(0),
1386 pn_time(0),
1387 );
1388 assert!(acked.is_empty());
1389 assert!(lost.is_empty());
1390 }
1391
1392 #[test]
1393 fn drop_spaces() {
1394 let mut lr = Fixture::default();
1395 lr.on_packet_sent(
1396 SentPacket::new(
1397 PacketType::Initial,
1398 0,
1399 pn_time(0),
1400 true,
1401 Vec::new(),
1402 ON_SENT_SIZE,
1403 ),
1404 Instant::now(),
1405 );
1406 lr.on_packet_sent(
1407 SentPacket::new(
1408 PacketType::Handshake,
1409 0,
1410 pn_time(1),
1411 true,
1412 Vec::new(),
1413 ON_SENT_SIZE,
1414 ),
1415 Instant::now(),
1416 );
1417 lr.on_packet_sent(
1418 SentPacket::new(
1419 PacketType::Short,
1420 0,
1421 pn_time(2),
1422 true,
1423 Vec::new(),
1424 ON_SENT_SIZE,
1425 ),
1426 Instant::now(),
1427 );
1428
1429 // Now put all spaces on the LR timer so we can see them.
1430 for sp in &[
1431 PacketType::Initial,
1432 PacketType::Handshake,
1433 PacketType::Short,
1434 ] {
1435 let sent_pkt = SentPacket::new(*sp, 1, pn_time(3), true, Vec::new(), ON_SENT_SIZE);
1436 let pn_space = PacketNumberSpace::from(sent_pkt.packet_type());
1437 lr.on_packet_sent(sent_pkt, Instant::now());
1438 lr.on_ack_received(
1439 pn_space,
1440 vec![1..=1],
1441 None,
1442 Duration::from_secs(0),
1443 pn_time(3),
1444 );
1445 let mut lost = Vec::new();
1446 lr.spaces.get_mut(pn_space).unwrap().detect_lost_packets(
1447 pn_time(3),
1448 TEST_RTT,
1449 TEST_RTT * 3, // unused
1450 &mut lost,
1451 );
1452 assert!(lost.is_empty());
1453 }
1454
1455 lr.discard(PacketNumberSpace::Initial, pn_time(3));
1456 assert_sent_times(&lr, None, Some(pn_time(1)), Some(pn_time(2)));
1457
1458 lr.discard(PacketNumberSpace::Handshake, pn_time(3));
1459 assert_sent_times(&lr, None, None, Some(pn_time(2)));
1460
1461 // There are cases where we send a packet that is not subsequently tracked.
1462 // So check that this works.
1463 lr.on_packet_sent(
1464 SentPacket::new(
1465 PacketType::Initial,
1466 0,
1467 pn_time(3),
1468 true,
1469 Vec::new(),
1470 ON_SENT_SIZE,
1471 ),
1472 Instant::now(),
1473 );
1474 assert_sent_times(&lr, None, None, Some(pn_time(2)));
1475 }
1476
1477 #[test]
1478 fn rearm_pto_after_confirmed() {
1479 let mut lr = Fixture::default();
1480 lr.on_packet_sent(
1481 SentPacket::new(
1482 PacketType::Initial,
1483 0,
1484 now(),
1485 true,
1486 Vec::new(),
1487 ON_SENT_SIZE,
1488 ),
1489 Instant::now(),
1490 );
1491 // Set the RTT to the initial value so that discarding doesn't
1492 // alter the estimate.
1493 let rtt = lr.path.borrow().rtt().estimate();
1494 lr.on_ack_received(
1495 PacketNumberSpace::Initial,
1496 vec![0..=0],
1497 None,
1498 Duration::new(0, 0),
1499 now() + rtt,
1500 );
1501
1502 lr.on_packet_sent(
1503 SentPacket::new(
1504 PacketType::Handshake,
1505 0,
1506 now(),
1507 true,
1508 Vec::new(),
1509 ON_SENT_SIZE,
1510 ),
1511 Instant::now(),
1512 );
1513 lr.on_packet_sent(
1514 SentPacket::new(PacketType::Short, 0, now(), true, Vec::new(), ON_SENT_SIZE),
1515 Instant::now(),
1516 );
1517
1518 assert!(lr.pto_time(PacketNumberSpace::ApplicationData).is_some());
1519 lr.discard(PacketNumberSpace::Initial, pn_time(1));
1520 assert!(lr.pto_time(PacketNumberSpace::ApplicationData).is_some());
1521
1522 // Expiring state after the PTO on the ApplicationData space has
1523 // expired should result in setting a PTO state.
1524 let default_pto = lr.path.borrow().rtt().pto(true);
1525 let expected_pto = pn_time(2) + default_pto;
1526 lr.discard(PacketNumberSpace::Handshake, expected_pto);
1527 let profile = lr.send_profile(now());
1528 assert!(profile.pto.is_some());
1529 assert!(!profile.should_probe(PacketNumberSpace::Initial));
1530 assert!(!profile.should_probe(PacketNumberSpace::Handshake));
1531 assert!(profile.should_probe(PacketNumberSpace::ApplicationData));
1532 }
1533
1534 #[test]
1535 fn no_pto_if_amplification_limited() {
1536 let mut lr = Fixture::default();
1537 // Eat up the amplification limit by telling the path that we've sent a giant packet.
1538 {
1539 const SPARE: usize = 10;
1540 let mut path = lr.path.borrow_mut();
1541 let limit = path.amplification_limit();
1542 path.add_sent(limit - SPARE);
1543 assert_eq!(path.amplification_limit(), SPARE);
1544 }
1545
1546 lr.on_packet_sent(
1547 SentPacket::new(
1548 PacketType::Initial,
1549 0,
1550 now(),
1551 true,
1552 Vec::new(),
1553 ON_SENT_SIZE,
1554 ),
1555 Instant::now(),
1556 );
1557
1558 let handshake_pto = lr.path.borrow().rtt().pto(false);
1559 let expected_pto = now() + handshake_pto;
1560 assert_eq!(lr.pto_time(PacketNumberSpace::Initial), Some(expected_pto));
1561 let profile = lr.send_profile(now());
1562 assert!(profile.ack_only(PacketNumberSpace::Initial));
1563 assert!(profile.pto.is_none());
1564 assert!(!profile.should_probe(PacketNumberSpace::Initial));
1565 assert!(!profile.should_probe(PacketNumberSpace::Handshake));
1566 assert!(!profile.should_probe(PacketNumberSpace::ApplicationData));
1567 }
1568 }