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