Debian Codegraph @

third_party/rust/neqo-transport/src/tracking.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 received packets and generating ACKs thereof.
8
9 use std::{
10 cmp::min,
11 collections::VecDeque,
12 fmt::{self, Display, Formatter},
13 time::{Duration, Instant},
14 };
15
16 use enum_map::{Enum, EnumMap};
17 use enumset::{EnumSet, EnumSetType};
18 use log::{log_enabled, Level};
19 use neqo_common::{qdebug, qinfo, qtrace, qwarn, IpTosEcn, MAX_VARINT};
20 use neqo_crypto::Epoch;
21 use strum::{Display, EnumIter};
22
23 use crate::{
24 ecn,
25 frame::FrameType,
26 packet::{PacketBuilder, PacketNumber, PacketType},
27 recovery::RecoveryToken,
28 stats::FrameStats,
29 Error, Res,
30 };
31
32 #[derive(Debug, PartialOrd, Ord, EnumSetType, Enum, EnumIter, Display)]
33 pub enum PacketNumberSpace {
34 #[strum(to_string = "in")]
35 Initial,
36 #[strum(to_string = "hs")]
37 Handshake,
38 #[strum(to_string = "ap")]
39 ApplicationData,
40 }
41
42 impl From<Epoch> for PacketNumberSpace {
43 fn from(epoch: Epoch) -> Self {
44 match epoch {
45 Epoch::Initial => Self::Initial,
46 Epoch::Handshake => Self::Handshake,
47 Epoch::ApplicationData | Epoch::ZeroRtt => Self::ApplicationData,
48 }
49 }
50 }
51
52 impl From<PacketNumberSpace> for Epoch {
53 fn from(val: PacketNumberSpace) -> Self {
54 match val {
55 PacketNumberSpace::Initial => Self::Initial,
56 PacketNumberSpace::Handshake => Self::Handshake,
57 PacketNumberSpace::ApplicationData => Self::ApplicationData,
58 }
59 }
60 }
61
62 #[expect(clippy::fallible_impl_from, reason = "OK here.")]
63 impl From<PacketType> for PacketNumberSpace {
64 fn from(pt: PacketType) -> Self {
65 match pt {
66 PacketType::Initial => Self::Initial,
67 PacketType::Handshake => Self::Handshake,
68 PacketType::ZeroRtt | PacketType::Short => Self::ApplicationData,
69 _ => panic!("Attempted to get space from wrong packet type"),
70 }
71 }
72 }
73
74 pub type PacketNumberSpaceSet = EnumSet<PacketNumberSpace>;
75
76 /// `InsertionResult` tracks whether something was inserted for `PacketRange::add()`.
77 pub enum InsertionResult {
78 Largest,
79 Smallest,
80 NotInserted,
81 }
82
83 #[derive(Clone, Debug, Default)]
84 pub struct PacketRange {
85 largest: PacketNumber,
86 smallest: PacketNumber,
87 ack_needed: bool,
88 }
89
90 impl PacketRange {
91 /// Make a single packet range.
92 pub const fn new(pn: PacketNumber) -> Self {
93 Self {
94 largest: pn,
95 smallest: pn,
96 ack_needed: true,
97 }
98 }
99
100 /// Get the number of acknowledged packets in the range.
101 pub const fn len(&self) -> u64 {
102 self.largest - self.smallest + 1
103 }
104
105 /// Returns whether this needs to be sent.
106 pub const fn ack_needed(&self) -> bool {
107 self.ack_needed
108 }
109
110 /// Return whether the given number is in the range.
111 pub const fn contains(&self, pn: PacketNumber) -> bool {
112 (pn >= self.smallest) && (pn <= self.largest)
113 }
114
115 /// Maybe add a packet number to the range. Returns true if it was added
116 /// at the small end (which indicates that this might need merging with a
117 /// preceding range).
118 pub fn add(&mut self, pn: PacketNumber) -> InsertionResult {
119 assert!(!self.contains(pn));
120 // Only insert if this is adjacent the current range.
121 if (self.largest + 1) == pn {
122 qtrace!("[{self}] Adding largest {pn}");
123 self.largest += 1;
124 self.ack_needed = true;
125 InsertionResult::Largest
126 } else if self.smallest == (pn + 1) {
127 qtrace!("[{self}] Adding smallest {pn}");
128 self.smallest -= 1;
129 self.ack_needed = true;
130 InsertionResult::Smallest
131 } else {
132 InsertionResult::NotInserted
133 }
134 }
135
136 /// Maybe merge a higher-numbered range into this.
137 fn merge_larger(&mut self, other: &Self) {
138 qinfo!("[{self}] Merging {other}");
139 // This only works if they are immediately adjacent.
140 assert_eq!(self.largest + 1, other.smallest);
141
142 self.largest = other.largest;
143 self.ack_needed = self.ack_needed || other.ack_needed;
144 }
145
146 /// When a packet containing the range `other` is acknowledged,
147 /// clear the `ack_needed` attribute on this.
148 /// Requires that other is equal to this, or a larger range.
149 pub fn acknowledged(&mut self, other: &Self) {
150 if (other.smallest <= self.smallest) && (other.largest >= self.largest) {
151 self.ack_needed = false;
152 }
153 }
154 }
155
156 impl Display for PacketRange {
157 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
158 write!(f, "{}->{}", self.largest, self.smallest)
159 }
160 }
161
162 /// The default maximum ACK delay we use locally and advertise to the remote.
163 pub const DEFAULT_LOCAL_ACK_DELAY: Duration = Duration::from_millis(20);
164 /// The default maximum ACK delay we assume the remote uses.
165 ///
166 /// > If this value is absent, a default of 25 milliseconds is assumed.
167 ///
168 /// <https://datatracker.ietf.org/doc/html/rfc9000#section-18.2>
169 pub const DEFAULT_REMOTE_ACK_DELAY: Duration = Duration::from_millis(25);
170 /// The default number of in-order packets we will receive after
171 /// largest acknowledged without sending an immediate acknowledgment.
172 pub const DEFAULT_ACK_PACKET_TOLERANCE: PacketNumber = 1;
173 const MAX_TRACKED_RANGES: usize = 32;
174 const MAX_ACKS_PER_FRAME: usize = 32;
175
176 /// A structure that tracks what was included in an ACK.
177 #[derive(Debug, Clone)]
178 pub struct AckToken {
179 space: PacketNumberSpace,
180 ranges: Vec<PacketRange>,
181 }
182
183 impl AckToken {
184 /// Get the space for this token.
185 pub const fn space(&self) -> PacketNumberSpace {
186 self.space
187 }
188 }
189
190 /// A structure that tracks what packets have been received,
191 /// and what needs acknowledgement for a packet number space.
192 #[derive(Debug)]
193 pub struct RecvdPackets {
194 space: PacketNumberSpace,
195 ranges: VecDeque<PacketRange>,
196 /// The packet number of the lowest number packet that we are tracking.
197 min_tracked: PacketNumber,
198 /// The time we got the largest acknowledged.
199 largest_pn_time: Option<Instant>,
200 /// The time that we should be sending an ACK.
201 ack_time: Option<Instant>,
202 /// The time we last sent an ACK.
203 last_ack_time: Option<Instant>,
204 /// The current ACK frequency sequence number.
205 ack_frequency_seqno: u64,
206 /// The time to delay after receiving the first packet that is
207 /// not immediately acknowledged.
208 ack_delay: Duration,
209 /// The number of ack-eliciting packets that have been received, but
210 /// not acknowledged.
211 unacknowledged_count: PacketNumber,
212 /// The number of contiguous packets that can be received without
213 /// acknowledging immediately.
214 unacknowledged_tolerance: PacketNumber,
215 /// Whether we are ignoring packets that arrive out of order
216 /// for the purposes of generating immediate acknowledgment.
217 ignore_order: bool,
218 // The counts of different ECN marks that have been received.
219 ecn_count: ecn::Count,
220 }
221
222 impl RecvdPackets {
223 /// Make a new `RecvdPackets` for the indicated packet number space.
224 pub fn new(space: PacketNumberSpace) -> Self {
225 Self {
226 space,
227 ranges: VecDeque::new(),
228 min_tracked: 0,
229 largest_pn_time: None,
230 ack_time: None,
231 last_ack_time: None,
232 ack_frequency_seqno: 0,
233 ack_delay: DEFAULT_LOCAL_ACK_DELAY,
234 unacknowledged_count: 0,
235 unacknowledged_tolerance: if space == PacketNumberSpace::ApplicationData {
236 DEFAULT_ACK_PACKET_TOLERANCE
237 } else {
238 // ACK more aggressively
239 0
240 },
241 ignore_order: false,
242 ecn_count: ecn::Count::default(),
243 }
244 }
245
246 /// Get the ECN counts.
247 pub fn ecn_marks(&mut self) -> &mut ecn::Count {
248 &mut self.ecn_count
249 }
250
251 /// Get the time at which the next ACK should be sent.
252 pub const fn ack_time(&self) -> Option<Instant> {
253 self.ack_time
254 }
255
256 /// Update acknowledgment delay parameters.
257 pub fn ack_freq(
258 &mut self,
259 seqno: u64,
260 tolerance: PacketNumber,
261 delay: Duration,
262 ignore_order: bool,
263 ) {
264 // Yes, this means that we will overwrite values if a sequence number is
265 // reused, but that is better than using an `Option<PacketNumber>`
266 // when it will always be `Some`.
267 if seqno >= self.ack_frequency_seqno {
268 self.ack_frequency_seqno = seqno;
269 self.unacknowledged_tolerance = tolerance;
270 self.ack_delay = delay;
271 self.ignore_order = ignore_order;
272 }
273 }
274
275 /// Returns true if an ACK frame should be sent now.
276 fn ack_now(&self, now: Instant, rtt: Duration) -> bool {
277 // If ack_time is Some, then we have something to acknowledge.
278 // In that case, either ack because `now >= ack_time`, or
279 // because it is more than an RTT since the last time we sent an ack.
280 self.ack_time.is_some_and(|next| {
281 next <= now || self.last_ack_time.is_some_and(|last| last + rtt <= now)
282 })
283 }
284
285 // A simple addition of a packet number to the tracked set.
286 // This doesn't do a binary search on the assumption that
287 // new packets will generally be added to the start of the list.
288 fn add(&mut self, pn: PacketNumber) -> Res<()> {
289 for i in 0..self.ranges.len() {
290 match self.ranges[i].add(pn) {
291 InsertionResult::Largest => return Ok(()),
292 InsertionResult::Smallest => {
293 // If this was the smallest, it might have filled a gap.
294 let nxt = i + 1;
295 if (nxt < self.ranges.len()) && (pn - 1 == self.ranges[nxt].largest) {
296 let larger = self.ranges.remove(i).ok_or(Error::InternalError)?;
297 self.ranges[i].merge_larger(&larger);
298 }
299 return Ok(());
300 }
301 InsertionResult::NotInserted => {
302 if self.ranges[i].largest < pn {
303 self.ranges.insert(i, PacketRange::new(pn));
304 return Ok(());
305 }
306 }
307 }
308 }
309 self.ranges.push_back(PacketRange::new(pn));
310 Ok(())
311 }
312
313 fn trim_ranges(&mut self) -> Res<()> {
314 // Limit the number of ranges that are tracked to MAX_TRACKED_RANGES.
315 if self.ranges.len() > MAX_TRACKED_RANGES {
316 let oldest = self.ranges.pop_back().ok_or(Error::InternalError)?;
317 if oldest.ack_needed {
318 qwarn!("[{self}] Dropping unacknowledged ACK range: {oldest}");
319 // TODO(mt) Record some statistics about this so we can tune MAX_TRACKED_RANGES.
320 } else {
321 qdebug!("[{self}] Drop ACK range: {oldest}");
322 }
323 self.min_tracked = oldest.largest + 1;
324 }
325 Ok(())
326 }
327
328 /// Add the packet to the tracked set.
329 /// Return true if the packet was the largest received so far.
330 pub fn set_received(
331 &mut self,
332 now: Instant,
333 pn: PacketNumber,
334 ack_eliciting: bool,
335 ) -> Res<bool> {
336 let next_in_order_pn = self.ranges.front().map_or(0, |r| r.largest + 1);
337 qtrace!("[{self}] received {pn}, next: {next_in_order_pn}");
338
339 self.add(pn)?;
340 self.trim_ranges()?;
341
342 // The new addition was the largest, so update the time we use for calculating ACK delay.
343 let largest = if pn >= next_in_order_pn {
344 self.largest_pn_time = Some(now);
345 true
346 } else {
347 false
348 };
349
350 if ack_eliciting {
351 self.unacknowledged_count += 1;
352
353 let immediate_ack = self.space != PacketNumberSpace::ApplicationData
354 || (pn != next_in_order_pn && !self.ignore_order)
355 || self.unacknowledged_count > self.unacknowledged_tolerance;
356
357 let ack_time = if immediate_ack {
358 now
359 } else {
360 // Note that `ack_delay` can change and that won't take effect if
361 // we are waiting on the previous delay timer.
362 // If ACK delay increases, we might send an ACK a bit early;
363 // if ACK delay decreases, we might send an ACK a bit later.
364 // We could use min() here, but change is rare and the size
365 // of the change is very small.
366 self.ack_time.unwrap_or_else(|| now + self.ack_delay)
367 };
368 qdebug!("[{self}] Set ACK timer to {ack_time:?}");
369 self.ack_time = Some(ack_time);
370 }
371 Ok(largest)
372 }
373
374 /// If we just received a PING frame, we should immediately acknowledge.
375 pub fn immediate_ack(&mut self, now: Instant) {
376 self.ack_time = Some(now);
377 qdebug!("[{self}] immediate_ack at {now:?}");
378 }
379
380 /// Check if the packet is a duplicate.
381 pub fn is_duplicate(&self, pn: PacketNumber) -> bool {
382 if pn < self.min_tracked {
383 return true;
384 }
385 self.ranges
386 .iter()
387 .take_while(|r| pn <= r.largest)
388 .any(|r| r.contains(pn))
389 }
390
391 /// Mark the given range as having been acknowledged.
392 pub fn acknowledged(&mut self, acked: &[PacketRange]) {
393 let mut range_iter = self.ranges.iter_mut();
394 let mut cur = range_iter.next().expect("should have at least one range");
395 for ack in acked {
396 while cur.smallest > ack.largest {
397 cur = match range_iter.next() {
398 Some(c) => c,
399 None => return,
400 };
401 }
402 cur.acknowledged(ack);
403 }
404 }
405
406 /// Length of the worst possible ACK frame, assuming only one range and ECN counts.
407 /// Note that this assumes one byte for the type and count of extra ranges.
408 pub const USEFUL_ACK_LEN: usize = 1 + 8 + 8 + 1 + 8 + 3 * 8;
409
410 /// Generate an ACK frame for this packet number space.
411 ///
412 /// Unlike other frame generators this doesn't modify the underlying instance
413 /// to track what has been sent. This only clears the delayed ACK timer.
414 ///
415 /// When sending ACKs, we want to always send the most recent ranges,
416 /// even if they have been sent in other packets.
417 ///
418 /// We don't send ranges that have been acknowledged, but they still need
419 /// to be tracked so that duplicates can be detected.
420 fn write_frame(
421 &mut self,
422 now: Instant,
423 rtt: Duration,
424 builder: &mut PacketBuilder,
425 tokens: &mut Vec<RecoveryToken>,
426 stats: &mut FrameStats,
427 ) {
428 // Check that we aren't delaying ACKs.
429 if !self.ack_now(now, rtt) {
430 return;
431 }
432
433 // Drop extra ACK ranges to fit the available space. Do this based on
434 // a worst-case estimate of frame size for simplicity.
435 //
436 // When congestion limited, ACK-only packets are 255 bytes at most
437 // (`recovery::ACK_ONLY_SIZE_LIMIT - 1`). This results in limiting the
438 // ranges to 13 here.
439 let max_ranges = if let Some(avail) = builder.remaining().checked_sub(Self::USEFUL_ACK_LEN)
440 {
441 // Apply a hard maximum to keep plenty of space for other stuff.
442 min(1 + (avail / 16), MAX_ACKS_PER_FRAME)
443 } else {
444 return;
445 };
446
447 let ranges = self
448 .ranges
449 .iter()
450 .filter(|r| r.ack_needed())
451 .take(max_ranges)
452 .cloned()
453 .collect::<Vec<_>>();
454 if ranges.is_empty() {
455 return;
456 }
457
458 builder.encode_varint(if self.ecn_count.is_some() {
459 FrameType::AckEcn
460 } else {
461 FrameType::Ack
462 });
463 let mut iter = ranges.iter();
464 let Some(first) = iter.next() else { return };
465 builder.encode_varint(first.largest);
466 stats.largest_acknowledged = first.largest;
467 stats.ack += 1;
468
469 let Some(largest_pn_time) = self.largest_pn_time else {
470 return;
471 };
472 let elapsed = now.duration_since(largest_pn_time);
473 // We use the default exponent, so delay is in multiples of 8 microseconds.
474 let ack_delay = u64::try_from(elapsed.as_micros() / 8).unwrap_or(u64::MAX);
475 let ack_delay = min(MAX_VARINT, ack_delay);
476 builder.encode_varint(ack_delay);
477 let Ok(extra_ranges) = u64::try_from(ranges.len() - 1) else {
478 return;
479 };
480 builder.encode_varint(extra_ranges); // extra ranges
481 builder.encode_varint(first.len() - 1); // first range
482
483 let mut last = first.smallest;
484 for r in iter {
485 // the difference must be at least 2 because 0-length gaps,
486 // (difference 1) are illegal.
487 builder.encode_varint(last - r.largest - 2); // Gap
488 builder.encode_varint(r.len() - 1); // Range
489 last = r.smallest;
490 }
491
492 if self.ecn_count.is_some() {
493 builder.encode_varint(self.ecn_count[IpTosEcn::Ect0]);
494 builder.encode_varint(self.ecn_count[IpTosEcn::Ect1]);
495 builder.encode_varint(self.ecn_count[IpTosEcn::Ce]);
496 }
497
498 // We've sent an ACK, reset the timer.
499 self.ack_time = None;
500 self.last_ack_time = Some(now);
501 self.unacknowledged_count = 0;
502
503 tokens.push(RecoveryToken::Ack(AckToken {
504 space: self.space,
505 ranges,
506 }));
507 }
508 }
509
510 impl Display for RecvdPackets {
511 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
512 write!(f, "Recvd-{}", self.space)
513 }
514 }
515
516 pub struct AckTracker {
517 spaces: EnumMap<PacketNumberSpace, Option<RecvdPackets>>,
518 }
519
520 impl AckTracker {
521 pub fn drop_space(&mut self, space: PacketNumberSpace) {
522 assert_ne!(
523 space,
524 PacketNumberSpace::ApplicationData,
525 "discarding application space"
526 );
527 if space == PacketNumberSpace::Handshake {
528 assert!(self.spaces[PacketNumberSpace::Initial].is_none());
529 }
530 self.spaces[space].take();
531 }
532
533 pub fn get_mut(&mut self, space: PacketNumberSpace) -> Option<&mut RecvdPackets> {
534 self.spaces[space].as_mut()
535 }
536
537 pub fn ack_freq(
538 &mut self,
539 seqno: u64,
540 tolerance: PacketNumber,
541 delay: Duration,
542 ignore_order: bool,
543 ) {
544 // Only ApplicationData ever delays ACK.
545 if let Some(space) = self.get_mut(PacketNumberSpace::ApplicationData) {
546 space.ack_freq(seqno, tolerance, delay, ignore_order);
547 }
548 }
549
550 /// Force an ACK to be generated immediately.
551 pub fn immediate_ack(&mut self, space: PacketNumberSpace, now: Instant) {
552 if let Some(space) = self.get_mut(space) {
553 space.immediate_ack(now);
554 }
555 }
556
557 /// Determine the earliest time that an ACK might be needed.
558 pub fn ack_time(&self, now: Instant) -> Option<Instant> {
559 if log_enabled!(Level::Trace) {
560 for (space, recvd) in &self.spaces {
561 if let Some(recvd) = recvd {
562 qtrace!("ack_time for {space} = {:?}", recvd.ack_time());
563 }
564 }
565 }
566 if self.spaces[PacketNumberSpace::Initial].is_none()
567 && self.spaces[PacketNumberSpace::Handshake].is_none()
568 {
569 if let Some(recvd) = &self.spaces[PacketNumberSpace::ApplicationData] {
570 return recvd.ack_time();
571 }
572 }
573
574 // Ignore any time that is in the past relative to `now`.
575 // That is something of a hack, but there are cases where we can't send ACK
576 // frames for all spaces, which can mean that one space is stuck in the past.
577 // That isn't a problem because we guarantee that earlier spaces will always
578 // be able to send ACK frames.
579 self.spaces
580 .values()
581 .flatten()
582 .filter_map(|recvd| recvd.ack_time().filter(|t| *t > now))
583 .min()
584 }
585
586 pub fn acked(&mut self, token: &AckToken) {
587 if let Some(space) = self.get_mut(token.space) {
588 space.acknowledged(&token.ranges);
589 }
590 }
591
592 pub(crate) fn write_frame(
593 &mut self,
594 pn_space: PacketNumberSpace,
595 now: Instant,
596 rtt: Duration,
597 builder: &mut PacketBuilder,
598 tokens: &mut Vec<RecoveryToken>,
599 stats: &mut FrameStats,
600 ) {
601 if let Some(space) = self.get_mut(pn_space) {
602 space.write_frame(now, rtt, builder, tokens, stats);
603 }
604 }
605 }
606
607 impl Default for AckTracker {
608 fn default() -> Self {
609 Self {
610 spaces: EnumMap::from_array([
611 Some(RecvdPackets::new(PacketNumberSpace::Initial)),
612 Some(RecvdPackets::new(PacketNumberSpace::Handshake)),
613 Some(RecvdPackets::new(PacketNumberSpace::ApplicationData)),
614 ]),
615 }
616 }
617 }
618
619 #[cfg(test)]
620 mod tests {
621 use std::collections::HashSet;
622
623 use neqo_common::Encoder;
624 use test_fixture::now;
625
626 use super::{
627 AckTracker, Duration, Instant, PacketNumberSpace, RecoveryToken, RecvdPackets,
628 MAX_TRACKED_RANGES,
629 };
630 use crate::{
631 frame::Frame,
632 packet::{PacketBuilder, PacketNumber, PacketType},
633 stats::FrameStats,
634 };
635
636 const RTT: Duration = Duration::from_millis(100);
637
638 fn test_ack_range(pns: &[PacketNumber], nranges: usize) {
639 let mut rp = RecvdPackets::new(PacketNumberSpace::Initial); // Any space will do.
640 let mut packets = HashSet::new();
641
642 for pn in pns {
643 rp.set_received(now(), *pn, true).unwrap();
644 packets.insert(*pn);
645 }
646
647 assert_eq!(rp.ranges.len(), nranges);
648
649 // Check that all these packets will be detected as duplicates.
650 for pn in pns {
651 assert!(rp.is_duplicate(*pn));
652 }
653
654 // Check that the ranges decrease monotonically and don't overlap.
655 let mut iter = rp.ranges.iter();
656 let mut last = iter.next().expect("should have at least one");
657 for n in iter {
658 assert!(n.largest + 1 < last.smallest);
659 last = n;
660 }
661
662 // Check that the ranges include the right values.
663 let mut in_ranges = HashSet::new();
664 for range in &rp.ranges {
665 for included in range.smallest..=range.largest {
666 in_ranges.insert(included);
667 }
668 }
669 assert_eq!(packets, in_ranges);
670 }
671
672 #[test]
673 fn pn0() {
674 test_ack_range(&[0], 1);
675 }
676
677 #[test]
678 fn pn1() {
679 test_ack_range(&[1], 1);
680 }
681
682 #[test]
683 fn two_ranges() {
684 test_ack_range(&[0, 1, 2, 5, 6, 7], 2);
685 }
686
687 #[test]
688 fn fill_in_range() {
689 test_ack_range(&[0, 1, 2, 5, 6, 7, 3, 4], 1);
690 }
691
692 #[test]
693 fn too_many_ranges() {
694 let mut rp = RecvdPackets::new(PacketNumberSpace::Initial); // Any space will do.
695
696 // This will add one too many disjoint ranges.
697 for i in 0..=MAX_TRACKED_RANGES {
698 rp.set_received(now(), (i * 2) as u64, true).unwrap();
699 }
700
701 assert_eq!(rp.ranges.len(), MAX_TRACKED_RANGES);
702 assert_eq!(rp.ranges.back().unwrap().largest, 2);
703
704 // Even though the range was dropped, we still consider it a duplicate.
705 assert!(rp.is_duplicate(0));
706 assert!(!rp.is_duplicate(1));
707 assert!(rp.is_duplicate(2));
708 }
709
710 #[test]
711 fn ack_delay() {
712 const COUNT: PacketNumber = 9;
713 const DELAY: Duration = Duration::from_millis(7);
714 // Only application data packets are delayed.
715 let mut rp = RecvdPackets::new(PacketNumberSpace::ApplicationData);
716 assert!(rp.ack_time().is_none());
717 assert!(!rp.ack_now(now(), RTT));
718
719 rp.ack_freq(0, COUNT, DELAY, false);
720
721 // Some packets won't cause an ACK to be needed.
722 for i in 0..COUNT {
723 rp.set_received(now(), i, true).unwrap();
724 assert_eq!(Some(now() + DELAY), rp.ack_time());
725 assert!(!rp.ack_now(now(), RTT));
726 assert!(rp.ack_now(now() + DELAY, RTT));
727 }
728
729 // Exceeding COUNT will move the ACK time to now.
730 rp.set_received(now(), COUNT, true).unwrap();
731 assert_eq!(Some(now()), rp.ack_time());
732 assert!(rp.ack_now(now(), RTT));
733 }
734
735 #[test]
736 fn no_ack_delay() {
737 for space in &[PacketNumberSpace::Initial, PacketNumberSpace::Handshake] {
738 let mut rp = RecvdPackets::new(*space);
739 assert!(rp.ack_time().is_none());
740 assert!(!rp.ack_now(now(), RTT));
741
742 // Any packet in these spaces is acknowledged straight away.
743 rp.set_received(now(), 0, true).unwrap();
744 assert_eq!(Some(now()), rp.ack_time());
745 assert!(rp.ack_now(now(), RTT));
746 }
747 }
748
749 #[test]
750 fn ooo_no_ack_delay_new() {
751 let mut rp = RecvdPackets::new(PacketNumberSpace::ApplicationData);
752 assert!(rp.ack_time().is_none());
753 assert!(!rp.ack_now(now(), RTT));
754
755 // Anything other than packet 0 is acknowledged immediately.
756 rp.set_received(now(), 1, true).unwrap();
757 assert_eq!(Some(now()), rp.ack_time());
758 assert!(rp.ack_now(now(), RTT));
759 }
760
761 fn write_frame_at(rp: &mut RecvdPackets, now: Instant) {
762 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
763 let mut stats = FrameStats::default();
764 let mut tokens = Vec::new();
765 rp.write_frame(now, RTT, &mut builder, &mut tokens, &mut stats);
766 assert!(!tokens.is_empty());
767 assert_eq!(stats.ack, 1);
768 }
769
770 fn write_frame(rp: &mut RecvdPackets) {
771 write_frame_at(rp, now());
772 }
773
774 #[test]
775 fn ooo_no_ack_delay_fill() {
776 let mut rp = RecvdPackets::new(PacketNumberSpace::ApplicationData);
777 rp.set_received(now(), 1, true).unwrap();
778 write_frame(&mut rp);
779
780 // Filling in behind the largest acknowledged causes immediate ACK.
781 rp.set_received(now(), 0, true).unwrap();
782 write_frame(&mut rp);
783
784 // Receiving the next packet won't elicit an ACK.
785 rp.set_received(now(), 2, true).unwrap();
786 assert!(!rp.ack_now(now(), RTT));
787 }
788
789 #[test]
790 fn immediate_ack_after_rtt() {
791 let mut rp = RecvdPackets::new(PacketNumberSpace::ApplicationData);
792 rp.set_received(now(), 1, true).unwrap();
793 write_frame(&mut rp);
794
795 // Filling in behind the largest acknowledged causes immediate ACK.
796 rp.set_received(now(), 0, true).unwrap();
797 write_frame(&mut rp);
798
799 // A new packet ordinarily doesn't result in an ACK, but this time it does.
800 rp.set_received(now() + RTT, 2, true).unwrap();
801 write_frame_at(&mut rp, now() + RTT);
802 }
803
804 #[test]
805 fn ooo_no_ack_delay_threshold_new() {
806 let mut rp = RecvdPackets::new(PacketNumberSpace::ApplicationData);
807
808 // Set tolerance to 2 and then it takes three packets.
809 rp.ack_freq(0, 2, Duration::from_millis(10), true);
810
811 rp.set_received(now(), 1, true).unwrap();
812 assert_ne!(Some(now()), rp.ack_time());
813 rp.set_received(now(), 2, true).unwrap();
814 assert_ne!(Some(now()), rp.ack_time());
815 rp.set_received(now(), 3, true).unwrap();
816 assert_eq!(Some(now()), rp.ack_time());
817 }
818
819 #[test]
820 fn ooo_no_ack_delay_threshold_gap() {
821 let mut rp = RecvdPackets::new(PacketNumberSpace::ApplicationData);
822 rp.set_received(now(), 1, true).unwrap();
823 write_frame(&mut rp);
824
825 // Set tolerance to 2 and then it takes three packets.
826 rp.ack_freq(0, 2, Duration::from_millis(10), true);
827
828 rp.set_received(now(), 3, true).unwrap();
829 assert_ne!(Some(now()), rp.ack_time());
830 rp.set_received(now(), 4, true).unwrap();
831 assert_ne!(Some(now()), rp.ack_time());
832 rp.set_received(now(), 5, true).unwrap();
833 assert_eq!(Some(now()), rp.ack_time());
834 }
835
836 /// Test that an in-order packet that is not ack-eliciting doesn't
837 /// increase the number of packets needed to cause an ACK.
838 #[test]
839 fn non_ack_eliciting_skip() {
840 let mut rp = RecvdPackets::new(PacketNumberSpace::ApplicationData);
841 rp.ack_freq(0, 1, Duration::from_millis(10), true);
842
843 // This should be ignored.
844 rp.set_received(now(), 0, false).unwrap();
845 assert_ne!(Some(now()), rp.ack_time());
846 // Skip 1 (it has no effect).
847 rp.set_received(now(), 2, true).unwrap();
848 assert_ne!(Some(now()), rp.ack_time());
849 rp.set_received(now(), 3, true).unwrap();
850 assert_eq!(Some(now()), rp.ack_time());
851 }
852
853 /// If a packet that is not ack-eliciting is reordered, that's fine too.
854 #[test]
855 fn non_ack_eliciting_reorder() {
856 let mut rp = RecvdPackets::new(PacketNumberSpace::ApplicationData);
857 rp.ack_freq(0, 1, Duration::from_millis(10), false);
858
859 // These are out of order, but they are not ack-eliciting.
860 rp.set_received(now(), 1, false).unwrap();
861 assert_ne!(Some(now()), rp.ack_time());
862 rp.set_received(now(), 0, false).unwrap();
863 assert_ne!(Some(now()), rp.ack_time());
864
865 // These are in order.
866 rp.set_received(now(), 2, true).unwrap();
867 assert_ne!(Some(now()), rp.ack_time());
868 rp.set_received(now(), 3, true).unwrap();
869 assert_eq!(Some(now()), rp.ack_time());
870 }
871
872 #[test]
873 fn aggregate_ack_time() {
874 const DELAY: Duration = Duration::from_millis(17);
875 let mut tracker = AckTracker::default();
876 tracker.ack_freq(0, 1, DELAY, false);
877 // This packet won't trigger an ACK.
878 tracker
879 .get_mut(PacketNumberSpace::Handshake)
880 .unwrap()
881 .set_received(now(), 0, false)
882 .unwrap();
883 assert_eq!(None, tracker.ack_time(now()));
884
885 // This should be delayed.
886 tracker
887 .get_mut(PacketNumberSpace::ApplicationData)
888 .unwrap()
889 .set_received(now(), 0, true)
890 .unwrap();
891 assert_eq!(Some(now() + DELAY), tracker.ack_time(now()));
892
893 // This should move the time forward.
894 let later = now() + (DELAY / 2);
895 tracker
896 .get_mut(PacketNumberSpace::Initial)
897 .unwrap()
898 .set_received(later, 0, true)
899 .unwrap();
900 assert_eq!(Some(later), tracker.ack_time(now()));
901 }
902
903 #[test]
904 #[should_panic(expected = "discarding application space")]
905 fn drop_app() {
906 let mut tracker = AckTracker::default();
907 tracker.drop_space(PacketNumberSpace::ApplicationData);
908 }
909
910 #[test]
911 fn drop_spaces() {
912 let mut tracker = AckTracker::default();
913 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
914 tracker
915 .get_mut(PacketNumberSpace::Initial)
916 .unwrap()
917 .set_received(now(), 0, true)
918 .unwrap();
919 // The reference time for `ack_time` has to be in the past or we filter out the timer.
920 assert!(tracker
921 .ack_time(now().checked_sub(Duration::from_millis(1)).unwrap())
922 .is_some());
923
924 let mut tokens = Vec::new();
925 let mut stats = FrameStats::default();
926 tracker.write_frame(
927 PacketNumberSpace::Initial,
928 now(),
929 RTT,
930 &mut builder,
931 &mut tokens,
932 &mut stats,
933 );
934 assert_eq!(stats.ack, 1);
935
936 // Mark another packet as received so we have cause to send another ACK in that space.
937 tracker
938 .get_mut(PacketNumberSpace::Initial)
939 .unwrap()
940 .set_received(now(), 1, true)
941 .unwrap();
942 assert!(tracker
943 .ack_time(now().checked_sub(Duration::from_millis(1)).unwrap())
944 .is_some());
945
946 // Now drop that space.
947 tracker.drop_space(PacketNumberSpace::Initial);
948
949 assert!(tracker.get_mut(PacketNumberSpace::Initial).is_none());
950 assert!(tracker
951 .ack_time(now().checked_sub(Duration::from_millis(1)).unwrap())
952 .is_none());
953 tracker.write_frame(
954 PacketNumberSpace::Initial,
955 now(),
956 RTT,
957 &mut builder,
958 &mut tokens,
959 &mut stats,
960 );
961 assert_eq!(stats.ack, 1);
962 if let RecoveryToken::Ack(tok) = &tokens[0] {
963 tracker.acked(tok); // Should be a noop.
964 } else {
965 panic!("not an ACK token");
966 }
967 }
968
969 #[test]
970 fn no_room_for_ack() {
971 let mut tracker = AckTracker::default();
972 tracker
973 .get_mut(PacketNumberSpace::Initial)
974 .unwrap()
975 .set_received(now(), 0, true)
976 .unwrap();
977 assert!(tracker
978 .ack_time(now().checked_sub(Duration::from_millis(1)).unwrap())
979 .is_some());
980
981 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
982 builder.set_limit(10);
983
984 let mut stats = FrameStats::default();
985 tracker.write_frame(
986 PacketNumberSpace::Initial,
987 now(),
988 RTT,
989 &mut builder,
990 &mut Vec::new(),
991 &mut stats,
992 );
993 assert_eq!(stats.ack, 0);
994 assert_eq!(builder.len(), 1); // Only the short packet header has been added.
995 }
996
997 #[test]
998 fn no_room_for_extra_range() {
999 let mut tracker = AckTracker::default();
1000 tracker
1001 .get_mut(PacketNumberSpace::Initial)
1002 .unwrap()
1003 .set_received(now(), 0, true)
1004 .unwrap();
1005 tracker
1006 .get_mut(PacketNumberSpace::Initial)
1007 .unwrap()
1008 .set_received(now(), 2, true)
1009 .unwrap();
1010 assert!(tracker
1011 .ack_time(now().checked_sub(Duration::from_millis(1)).unwrap())
1012 .is_some());
1013
1014 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
1015 // The code pessimistically assumes that each range needs 16 bytes to express.
1016 // So this won't be enough for a second range.
1017 builder.set_limit(RecvdPackets::USEFUL_ACK_LEN + 8);
1018
1019 let mut stats = FrameStats::default();
1020 tracker.write_frame(
1021 PacketNumberSpace::Initial,
1022 now(),
1023 RTT,
1024 &mut builder,
1025 &mut Vec::new(),
1026 &mut stats,
1027 );
1028 assert_eq!(stats.ack, 1);
1029
1030 let mut dec = builder.as_decoder();
1031 dec.skip(1); // Skip the short header.
1032 let frame = Frame::decode(&mut dec).unwrap();
1033 if let Frame::Ack { ack_ranges, .. } = frame {
1034 assert_eq!(ack_ranges.len(), 0);
1035 } else {
1036 panic!("not an ACK!");
1037 }
1038 }
1039
1040 #[test]
1041 fn ack_time_elapsed() {
1042 let mut tracker = AckTracker::default();
1043
1044 // While we have multiple PN spaces, we ignore ACK timers from the past.
1045 // Send out of order to cause the delayed ack timer to be set to `now()`.
1046 tracker
1047 .get_mut(PacketNumberSpace::ApplicationData)
1048 .unwrap()
1049 .set_received(now(), 3, true)
1050 .unwrap();
1051 assert!(tracker.ack_time(now() + Duration::from_millis(1)).is_none());
1052
1053 // When we are reduced to one space, that filter is off.
1054 tracker.drop_space(PacketNumberSpace::Initial);
1055 tracker.drop_space(PacketNumberSpace::Handshake);
1056 assert_eq!(
1057 tracker.ack_time(now() + Duration::from_millis(1)),
1058 Some(now())
1059 );
1060 }
1061
1062 #[test]
1063 fn from_packet_type() {
1064 assert_eq!(
1065 PacketNumberSpace::from(PacketType::Initial),
1066 PacketNumberSpace::Initial
1067 );
1068 assert_eq!(
1069 PacketNumberSpace::from(PacketType::Handshake),
1070 PacketNumberSpace::Handshake
1071 );
1072 assert_eq!(
1073 PacketNumberSpace::from(PacketType::ZeroRtt),
1074 PacketNumberSpace::ApplicationData
1075 );
1076 assert_eq!(
1077 PacketNumberSpace::from(PacketType::Short),
1078 PacketNumberSpace::ApplicationData
1079 );
1080 assert!(std::panic::catch_unwind(|| {
1081 PacketNumberSpace::from(PacketType::VersionNegotiation)
1082 })
1083 .is_err());
1084 }
1085 }