1use std::{
2 cmp,
3 collections::{BTreeMap, VecDeque},
4 mem,
5 ops::{Bound, Index, IndexMut, Range},
6};
7
8use rand::{Rng, RngExt};
9use rustc_hash::FxHashSet;
10use tracing::trace;
11
12use super::assembler::Assembler;
13use crate::{
14 Dir, Duration, Instant, SocketAddr, StreamId, TransportError, VarInt, cid_queue::CidQueue,
15 connection::StreamsState, crypto::Keys, frame, packet::SpaceId, range_set::ArrayRangeSet,
16 shared::IssuedCid,
17};
18
19pub(super) struct PacketSpace {
20 pub(super) crypto: Option<Keys>,
21 pub(super) dedup: Dedup,
22 pub(super) rx_packet: u64,
24
25 pub(super) pending: Retransmits,
27 pub(super) pending_acks: PendingAcks,
29
30 pub(super) next_packet_number: u64,
33 pub(super) largest_acked_packet: Option<u64>,
35 pub(super) largest_acked_packet_sent: Instant,
36 pub(super) largest_ack_eliciting_sent: u64,
38 pub(super) unacked_non_ack_eliciting_tail: u64,
40 pub(super) sent_packets: BTreeMap<u64, SentPacket>,
43 pub(super) ecn_counters: frame::EcnCounts,
45 pub(super) ecn_feedback: frame::EcnCounts,
52
53 pub(super) crypto_stream: Assembler,
55 pub(super) crypto_offset: u64,
57
58 pub(super) time_of_last_ack_eliciting_packet: Option<Instant>,
60 pub(super) loss_time: Option<Instant>,
64 pub(super) loss_probes: u32,
66 pub(super) ping_pending: bool,
67 pub(super) immediate_ack_pending: bool,
68 pub(super) sent_with_keys: u64,
70}
71
72impl PacketSpace {
73 pub(super) fn new(now: Instant) -> Self {
74 Self {
75 crypto: None,
76 dedup: Dedup::new(),
77 rx_packet: 0,
78
79 pending: Retransmits::default(),
80 pending_acks: PendingAcks::new(),
81
82 next_packet_number: 0,
83 largest_acked_packet: None,
84 largest_acked_packet_sent: now,
85 largest_ack_eliciting_sent: 0,
86 unacked_non_ack_eliciting_tail: 0,
87 sent_packets: BTreeMap::new(),
88 ecn_counters: frame::EcnCounts::ZERO,
89 ecn_feedback: frame::EcnCounts::ZERO,
90
91 crypto_stream: Assembler::new(),
92 crypto_offset: 0,
93
94 time_of_last_ack_eliciting_packet: None,
95 loss_time: None,
96 loss_probes: 0,
97 ping_pending: false,
98 immediate_ack_pending: false,
99 sent_with_keys: 0,
100 }
101 }
102
103 pub(super) fn maybe_queue_probe(
116 &mut self,
117 request_immediate_ack: bool,
118 streams: &StreamsState,
119 ) {
120 if self.loss_probes == 0 {
121 return;
122 }
123
124 if request_immediate_ack {
125 self.immediate_ack_pending = true;
128 }
129
130 if !self.pending.is_empty(streams) {
131 return;
133 }
134
135 for packet in self.sent_packets.values_mut() {
137 if !packet.retransmits.is_empty(streams) {
138 self.pending |= mem::take(&mut packet.retransmits);
141 return;
142 }
143 }
144
145 if !self.immediate_ack_pending {
149 self.ping_pending = true;
150 }
151 }
152
153 pub(super) fn get_tx_number(&mut self) -> u64 {
158 assert!(self.next_packet_number < 2u64.pow(62));
160 let x = self.next_packet_number;
161 self.next_packet_number += 1;
162 self.sent_with_keys += 1;
163 x
164 }
165
166 pub(super) fn can_send(&self, streams: &StreamsState) -> SendableFrames {
167 let acks = self.pending_acks.can_send();
168 let other =
169 !self.pending.is_empty(streams) || self.ping_pending || self.immediate_ack_pending;
170
171 SendableFrames { acks, other }
172 }
173
174 pub(super) fn detect_ecn(
176 &mut self,
177 newly_acked: u64,
178 ecn: frame::EcnCounts,
179 ) -> Result<bool, &'static str> {
180 let ect0_increase = ecn
181 .ect0
182 .checked_sub(self.ecn_feedback.ect0)
183 .ok_or("peer ECT(0) count regression")?;
184 let ect1_increase = ecn
185 .ect1
186 .checked_sub(self.ecn_feedback.ect1)
187 .ok_or("peer ECT(1) count regression")?;
188 let ce_increase = ecn
189 .ce
190 .checked_sub(self.ecn_feedback.ce)
191 .ok_or("peer CE count regression")?;
192 let total_increase = ect0_increase + ect1_increase + ce_increase;
193 if total_increase < newly_acked {
194 return Err("ECN bleaching");
195 }
196 if (ect0_increase + ce_increase) < newly_acked || ect1_increase != 0 {
197 return Err("ECN corruption");
198 }
199 self.ecn_feedback = ecn;
204 Ok(ce_increase != 0)
205 }
206
207 pub(super) fn take(&mut self, number: u64) -> Option<SentPacket> {
209 let packet = self.sent_packets.remove(&number)?;
210 if !packet.ack_eliciting && number > self.largest_ack_eliciting_sent {
211 self.unacked_non_ack_eliciting_tail =
212 self.unacked_non_ack_eliciting_tail.checked_sub(1).unwrap();
213 }
214 Some(packet)
215 }
216
217 pub(super) fn sent(&mut self, number: u64, packet: SentPacket) -> Option<SentPacket> {
219 const MAX_UNACKED_NON_ACK_ELICTING_TAIL: u64 = 1_000;
226
227 let mut forgotten = None;
228 if packet.ack_eliciting {
229 self.unacked_non_ack_eliciting_tail = 0;
230 self.largest_ack_eliciting_sent = number;
231 } else if self.unacked_non_ack_eliciting_tail > MAX_UNACKED_NON_ACK_ELICTING_TAIL {
232 let oldest_after_ack_eliciting = *self
233 .sent_packets
234 .range((
235 Bound::Excluded(self.largest_ack_eliciting_sent),
236 Bound::Unbounded,
237 ))
238 .next()
239 .unwrap()
240 .0;
241 let packet = self
246 .sent_packets
247 .remove(&oldest_after_ack_eliciting)
248 .unwrap();
249 debug_assert!(!packet.ack_eliciting);
250 forgotten = Some(packet);
251 } else {
252 self.unacked_non_ack_eliciting_tail += 1;
253 }
254
255 self.sent_packets.insert(number, packet);
256 forgotten
257 }
258
259 pub(super) fn has_in_flight(&self) -> bool {
261 self.sent_packets.values().any(|x| x.size != 0)
265 }
266}
267
268impl Index<SpaceId> for [PacketSpace; 3] {
269 type Output = PacketSpace;
270 fn index(&self, space: SpaceId) -> &PacketSpace {
271 &self.as_ref()[space as usize]
272 }
273}
274
275impl IndexMut<SpaceId> for [PacketSpace; 3] {
276 fn index_mut(&mut self, space: SpaceId) -> &mut PacketSpace {
277 &mut self.as_mut()[space as usize]
278 }
279}
280
281#[derive(Debug, Clone)]
283pub(super) struct SentPacket {
284 pub(super) path_generation: u64,
286 pub(super) time_sent: Instant,
288 pub(super) size: u16,
292 pub(super) ack_eliciting: bool,
294 pub(super) largest_acked: Option<u64>,
296 pub(super) retransmits: ThinRetransmits,
300 pub(super) stream_frames: frame::StreamMetaVec,
304}
305
306#[allow(unreachable_pub)] #[derive(Debug, Default, Clone)]
309pub struct Retransmits {
310 pub(super) max_data: bool,
311 pub(super) data_blocked: bool,
312 pub(super) max_stream_id: [bool; 2],
313 pub(super) reset_stream: Vec<(StreamId, VarInt)>,
314 pub(super) stop_sending: Vec<frame::StopSending>,
315 pub(super) max_stream_data: FxHashSet<StreamId>,
316 pub(super) stream_data_blocked: FxHashSet<StreamId>,
317 pub(super) crypto: VecDeque<frame::Crypto>,
318 pub(super) new_cids: Vec<IssuedCid>,
319 pub(super) retire_cids: Vec<u64>,
320 pub(super) ack_frequency: bool,
321 pub(super) handshake_done: bool,
322 pub(super) new_tokens: Vec<SocketAddr>,
339}
340
341impl Retransmits {
342 pub(super) fn retire_cids(&mut self, cids: Range<u64>) -> Result<(), TransportError> {
343 let num = cids.end.saturating_sub(cids.start);
345 if (self.retire_cids.len() as u64).saturating_add(num) > Self::MAX_PENDING_RETIRED_CIDS {
346 return Err(TransportError::CONNECTION_ID_LIMIT_ERROR(
347 "queued too many retired CIDs",
348 ));
349 }
350
351 self.retire_cids.extend(cids);
352 Ok(())
353 }
354
355 pub(super) fn is_empty(&self, streams: &StreamsState) -> bool {
356 !self.max_data
357 && !(self.data_blocked && streams.can_send_data_blocked())
358 && !self.max_stream_id.into_iter().any(|x| x)
359 && self.reset_stream.is_empty()
360 && self.stop_sending.is_empty()
361 && self
362 .max_stream_data
363 .iter()
364 .all(|&id| !streams.can_send_flow_control(id))
365 && self
366 .stream_data_blocked
367 .iter()
368 .all(|&id| streams.stream_data_blocked_limit(id).is_none())
369 && self.crypto.is_empty()
370 && self.new_cids.is_empty()
371 && self.retire_cids.is_empty()
372 && !self.ack_frequency
373 && !self.handshake_done
374 && self.new_tokens.is_empty()
375 }
376
377 const MAX_PENDING_RETIRED_CIDS: u64 = CidQueue::LEN as u64 * 10;
381}
382
383impl ::std::ops::BitOrAssign for Retransmits {
384 fn bitor_assign(&mut self, rhs: Self) {
385 self.max_data |= rhs.max_data;
388 self.data_blocked |= rhs.data_blocked;
389 for dir in Dir::iter() {
390 self.max_stream_id[dir as usize] |= rhs.max_stream_id[dir as usize];
391 }
392 self.reset_stream.extend_from_slice(&rhs.reset_stream);
393 self.stop_sending.extend_from_slice(&rhs.stop_sending);
394 self.max_stream_data.extend(&rhs.max_stream_data);
395 self.stream_data_blocked.extend(&rhs.stream_data_blocked);
396 for crypto in rhs.crypto.into_iter().rev() {
397 self.crypto.push_front(crypto);
398 }
399 self.new_cids.extend(&rhs.new_cids);
400 self.retire_cids.extend(rhs.retire_cids);
401 self.ack_frequency |= rhs.ack_frequency;
402 self.handshake_done |= rhs.handshake_done;
403 self.new_tokens.extend_from_slice(&rhs.new_tokens);
404 }
405}
406
407impl ::std::ops::BitOrAssign<ThinRetransmits> for Retransmits {
408 fn bitor_assign(&mut self, rhs: ThinRetransmits) {
409 if let Some(retransmits) = rhs.retransmits {
410 self.bitor_assign(*retransmits)
411 }
412 }
413}
414
415impl ::std::iter::FromIterator<Self> for Retransmits {
416 fn from_iter<T>(iter: T) -> Self
417 where
418 T: IntoIterator<Item = Self>,
419 {
420 let mut result = Self::default();
421 for packet in iter {
422 result |= packet;
423 }
424 result
425 }
426}
427
428#[derive(Debug, Default, Clone)]
430pub(super) struct ThinRetransmits {
431 retransmits: Option<Box<Retransmits>>,
432}
433
434impl ThinRetransmits {
435 pub(super) fn is_empty(&self, streams: &StreamsState) -> bool {
437 match &self.retransmits {
438 Some(retransmits) => retransmits.is_empty(streams),
439 None => true,
440 }
441 }
442
443 pub(super) fn get(&self) -> Option<&Retransmits> {
445 self.retransmits.as_deref()
446 }
447
448 pub(super) fn get_or_create(&mut self) -> &mut Retransmits {
452 if self.retransmits.is_none() {
453 self.retransmits = Some(Box::default());
454 }
455 self.retransmits.as_deref_mut().unwrap()
456 }
457}
458
459pub(super) struct Dedup {
471 window: Window,
472 next: u64,
474}
475
476type Window = u128;
481
482const WINDOW_SIZE: u64 = 1 + mem::size_of::<Window>() as u64 * 8;
484
485impl Dedup {
486 pub(super) fn new() -> Self {
488 Self { window: 0, next: 0 }
489 }
490
491 fn highest(&self) -> u64 {
493 self.next - 1
494 }
495
496 pub(super) fn insert(&mut self, packet: u64) -> bool {
500 if let Some(diff) = packet.checked_sub(self.next) {
501 self.window = ((self.window << 1) | 1)
503 .checked_shl(cmp::min(diff, u64::from(u32::MAX)) as u32)
504 .unwrap_or(0);
505 self.next = packet + 1;
506 false
507 } else if self.highest() - packet < WINDOW_SIZE {
508 if let Some(bit) = (self.highest() - packet).checked_sub(1) {
510 let mask = 1 << bit;
512 let duplicate = self.window & mask != 0;
513 self.window |= mask;
514 duplicate
515 } else {
516 true
518 }
519 } else {
520 true
522 }
523 }
524
525 fn smallest_missing_in_interval(&self, lower_bound: u64, upper_bound: u64) -> Option<u64> {
529 debug_assert!(lower_bound <= upper_bound);
530 debug_assert!(upper_bound <= self.highest());
531 const BITFIELD_SIZE: u64 = (mem::size_of::<Window>() * 8) as u64;
532
533 let lower_bound = lower_bound + 1;
537 let upper_bound = upper_bound.saturating_sub(1);
538
539 let start_offset = (self.highest() - upper_bound).max(1) - 1;
542 if start_offset >= BITFIELD_SIZE {
543 return None;
546 }
547
548 let end_offset_exclusive = self.highest().saturating_sub(lower_bound);
549
550 let range_len = end_offset_exclusive
553 .saturating_sub(start_offset)
554 .min(BITFIELD_SIZE);
555 if range_len == 0 {
556 return None;
557 }
558
559 let mask = if range_len == BITFIELD_SIZE {
562 u128::MAX
563 } else {
564 ((1u128 << range_len) - 1) << start_offset
565 };
566 let gaps = !self.window & mask;
567
568 let smallest_missing_offset = 128 - gaps.leading_zeros() as u64;
569 let smallest_missing_packet = self.highest() - smallest_missing_offset;
570
571 if smallest_missing_packet <= upper_bound {
572 Some(smallest_missing_packet)
573 } else {
574 None
575 }
576 }
577
578 fn missing_in_interval(&self, lower_bound: u64, upper_bound: u64) -> bool {
582 self.smallest_missing_in_interval(lower_bound, upper_bound)
583 .is_some()
584 }
585}
586
587#[derive(Clone, Copy, PartialEq, Eq, Debug)]
589pub(super) struct SendableFrames {
590 pub(super) acks: bool,
591 pub(super) other: bool,
592}
593
594impl SendableFrames {
595 pub(super) fn empty() -> Self {
597 Self {
598 acks: false,
599 other: false,
600 }
601 }
602
603 pub(super) fn is_empty(&self) -> bool {
605 !self.acks && !self.other
606 }
607}
608
609#[derive(Debug)]
610pub(super) struct PendingAcks {
611 immediate_ack_required: bool,
616 ack_eliciting_since_last_ack_sent: u64,
620 non_ack_eliciting_since_last_ack_sent: u64,
621 ack_eliciting_threshold: u64,
622 reordering_threshold: u64,
630 earliest_ack_eliciting_since_last_ack_sent: Option<Instant>,
633 ranges: ArrayRangeSet,
636 largest_packet: Option<(u64, Instant)>,
639 largest_ack_eliciting_packet: Option<u64>,
641 largest_acked: Option<u64>,
643}
644
645impl PendingAcks {
646 fn new() -> Self {
647 Self {
648 immediate_ack_required: false,
649 ack_eliciting_since_last_ack_sent: 0,
650 non_ack_eliciting_since_last_ack_sent: 0,
651 ack_eliciting_threshold: 1,
652 reordering_threshold: 1,
653 earliest_ack_eliciting_since_last_ack_sent: None,
654 ranges: ArrayRangeSet::default(),
655 largest_packet: None,
656 largest_ack_eliciting_packet: None,
657 largest_acked: None,
658 }
659 }
660
661 pub(super) fn set_ack_frequency_params(&mut self, frame: &frame::AckFrequency) {
662 self.ack_eliciting_threshold = frame.ack_eliciting_threshold.into_inner();
663 self.reordering_threshold = frame.reordering_threshold.into_inner();
664 }
665
666 pub(super) fn set_immediate_ack_required(&mut self) {
667 self.immediate_ack_required = true;
668 }
669
670 pub(super) fn on_max_ack_delay_timeout(&mut self) {
671 self.immediate_ack_required = self.ack_eliciting_since_last_ack_sent > 0;
672 }
673
674 pub(super) fn max_ack_delay_timeout(&self, max_ack_delay: Duration) -> Option<Instant> {
675 self.earliest_ack_eliciting_since_last_ack_sent
676 .map(|earliest_unacked| earliest_unacked + max_ack_delay)
677 }
678
679 pub(super) fn can_send(&self) -> bool {
681 self.immediate_ack_required && !self.ranges.is_empty()
682 }
683
684 pub(super) fn can_send_with_other_frames(&self) -> bool {
686 !self.ranges.is_empty()
687 }
688
689 pub(super) fn ack_delay(&self, now: Instant) -> Duration {
691 self.largest_packet
692 .map_or(Duration::default(), |(_, received)| now - received)
693 }
694
695 pub(super) fn packet_received(
699 &mut self,
700 now: Instant,
701 packet_number: u64,
702 ack_eliciting: bool,
703 dedup: &Dedup,
704 ) -> bool {
705 if !ack_eliciting {
706 self.non_ack_eliciting_since_last_ack_sent += 1;
707 return false;
708 }
709
710 let prev_largest_ack_eliciting = self.largest_ack_eliciting_packet.unwrap_or(0);
711
712 self.largest_ack_eliciting_packet = self
714 .largest_ack_eliciting_packet
715 .map(|pn| pn.max(packet_number))
716 .or(Some(packet_number));
717
718 self.ack_eliciting_since_last_ack_sent += 1;
720 self.immediate_ack_required |=
721 self.ack_eliciting_since_last_ack_sent > self.ack_eliciting_threshold;
722
723 self.immediate_ack_required |=
725 self.is_out_of_order(packet_number, prev_largest_ack_eliciting, dedup);
726
727 if self.earliest_ack_eliciting_since_last_ack_sent.is_none() && !self.can_send() {
729 self.earliest_ack_eliciting_since_last_ack_sent = Some(now);
730 return true;
731 }
732
733 false
734 }
735
736 fn is_out_of_order(
737 &self,
738 packet_number: u64,
739 prev_largest_ack_eliciting: u64,
740 dedup: &Dedup,
741 ) -> bool {
742 match self.reordering_threshold {
743 0 => false,
744 1 => {
745 packet_number < prev_largest_ack_eliciting
747 || dedup.missing_in_interval(prev_largest_ack_eliciting, packet_number)
748 }
749 _ => {
750 let Some((largest_acked, largest_unacked)) =
753 self.largest_acked.zip(self.largest_ack_eliciting_packet)
754 else {
755 return false;
756 };
757 if self.reordering_threshold > largest_acked {
758 return false;
759 }
760 let largest_reported = largest_acked - self.reordering_threshold + 1;
763 let Some(smallest_missing_unreported) =
764 dedup.smallest_missing_in_interval(largest_reported, largest_unacked)
765 else {
766 return false;
767 };
768 largest_unacked - smallest_missing_unreported >= self.reordering_threshold
769 }
770 }
771 }
772
773 pub(super) fn acks_sent(&mut self) {
777 self.immediate_ack_required = false;
787 self.ack_eliciting_since_last_ack_sent = 0;
788 self.non_ack_eliciting_since_last_ack_sent = 0;
789 self.earliest_ack_eliciting_since_last_ack_sent = None;
790 self.largest_acked = self.largest_ack_eliciting_packet;
791 }
792
793 pub(super) fn insert_one(&mut self, packet: u64, now: Instant) {
795 self.ranges.insert_one(packet);
796
797 if self.largest_packet.is_none_or(|(pn, _)| packet > pn) {
798 self.largest_packet = Some((packet, now));
799 }
800
801 if self.ranges.len() > MAX_ACK_BLOCKS {
802 self.ranges.pop_min();
803 }
804 }
805
806 pub(super) fn subtract_below(&mut self, max: u64) {
808 self.ranges.remove(0..(max + 1));
809 }
810
811 pub(super) fn ranges(&self) -> &ArrayRangeSet {
813 &self.ranges
814 }
815
816 pub(super) fn maybe_ack_non_eliciting(&mut self) {
822 const LAZY_ACK_THRESHOLD: u64 = 10;
827 if self.non_ack_eliciting_since_last_ack_sent > LAZY_ACK_THRESHOLD {
828 self.immediate_ack_required = true;
829 }
830 }
831}
832
833pub(super) struct PacketNumberFilter {
850 next_skipped_packet_number: u64,
852 prev_skipped_packet_number: Option<u64>,
854 exponent: u32,
856}
857
858impl PacketNumberFilter {
859 pub(super) fn new(rng: &mut (impl Rng + ?Sized)) -> Self {
860 let exponent = 6;
862 Self {
863 next_skipped_packet_number: rng.random_range(0..2u64.saturating_pow(exponent)),
864 prev_skipped_packet_number: None,
865 exponent,
866 }
867 }
868
869 #[cfg(test)]
870 pub(super) fn disabled() -> Self {
871 Self {
872 next_skipped_packet_number: u64::MAX,
873 prev_skipped_packet_number: None,
874 exponent: u32::MAX,
875 }
876 }
877
878 pub(super) fn peek(&self, space: &PacketSpace) -> u64 {
879 let n = space.next_packet_number;
880 if n != self.next_skipped_packet_number {
881 return n;
882 }
883 n + 1
884 }
885
886 pub(super) fn allocate(
887 &mut self,
888 rng: &mut (impl Rng + ?Sized),
889 space: &mut PacketSpace,
890 ) -> u64 {
891 let n = space.get_tx_number();
892 if n != self.next_skipped_packet_number {
893 return n;
894 }
895
896 trace!("skipping pn {n}");
897 self.prev_skipped_packet_number = Some(self.next_skipped_packet_number);
899 let next_exponent = self.exponent.saturating_add(1);
900 self.next_skipped_packet_number = rng
901 .random_range(2u64.saturating_pow(self.exponent)..2u64.saturating_pow(next_exponent));
902 self.exponent = next_exponent;
903
904 space.get_tx_number()
905 }
906
907 pub(super) fn check_ack(
908 &self,
909 space_id: SpaceId,
910 range: std::ops::RangeInclusive<u64>,
911 ) -> Result<(), TransportError> {
912 if space_id == SpaceId::Data
913 && self
914 .prev_skipped_packet_number
915 .is_some_and(|x| range.contains(&x))
916 {
917 return Err(TransportError::PROTOCOL_VIOLATION("unsent packet acked"));
918 }
919 Ok(())
920 }
921}
922
923const MAX_ACK_BLOCKS: usize = 64;
925
926#[cfg(test)]
927mod test {
928 use super::*;
929
930 #[test]
931 fn sanity() {
932 let mut dedup = Dedup::new();
933 assert!(!dedup.insert(0));
934 assert_eq!(dedup.next, 1);
935 assert_eq!(dedup.window, 0b1);
936 assert!(dedup.insert(0));
937 assert_eq!(dedup.next, 1);
938 assert_eq!(dedup.window, 0b1);
939 assert!(!dedup.insert(1));
940 assert_eq!(dedup.next, 2);
941 assert_eq!(dedup.window, 0b11);
942 assert!(!dedup.insert(2));
943 assert_eq!(dedup.next, 3);
944 assert_eq!(dedup.window, 0b111);
945 assert!(!dedup.insert(4));
946 assert_eq!(dedup.next, 5);
947 assert_eq!(dedup.window, 0b11110);
948 assert!(!dedup.insert(7));
949 assert_eq!(dedup.next, 8);
950 assert_eq!(dedup.window, 0b1111_0100);
951 assert!(dedup.insert(4));
952 assert!(!dedup.insert(3));
953 assert_eq!(dedup.next, 8);
954 assert_eq!(dedup.window, 0b1111_1100);
955 assert!(!dedup.insert(6));
956 assert_eq!(dedup.next, 8);
957 assert_eq!(dedup.window, 0b1111_1101);
958 assert!(!dedup.insert(5));
959 assert_eq!(dedup.next, 8);
960 assert_eq!(dedup.window, 0b1111_1111);
961 }
962
963 #[test]
964 fn happypath() {
965 let mut dedup = Dedup::new();
966 for i in 0..(2 * WINDOW_SIZE) {
967 assert!(!dedup.insert(i));
968 for j in 0..=i {
969 assert!(dedup.insert(j));
970 }
971 }
972 }
973
974 #[test]
975 fn jump() {
976 let mut dedup = Dedup::new();
977 dedup.insert(2 * WINDOW_SIZE);
978 assert!(dedup.insert(WINDOW_SIZE));
979 assert_eq!(dedup.next, 2 * WINDOW_SIZE + 1);
980 assert_eq!(dedup.window, 0);
981 assert!(!dedup.insert(WINDOW_SIZE + 1));
982 assert_eq!(dedup.next, 2 * WINDOW_SIZE + 1);
983 assert_eq!(dedup.window, 1 << (WINDOW_SIZE - 2));
984 }
985
986 #[test]
987 fn dedup_has_missing() {
988 let mut dedup = Dedup::new();
989
990 dedup.insert(0);
991 assert!(!dedup.missing_in_interval(0, 0));
992
993 dedup.insert(1);
994 assert!(!dedup.missing_in_interval(0, 1));
995
996 dedup.insert(3);
997 assert!(dedup.missing_in_interval(1, 3));
998
999 dedup.insert(4);
1000 assert!(!dedup.missing_in_interval(3, 4));
1001 assert!(dedup.missing_in_interval(0, 4));
1002
1003 dedup.insert(2);
1004 assert!(!dedup.missing_in_interval(0, 4));
1005 }
1006
1007 #[test]
1008 fn dedup_outside_of_window_has_missing() {
1009 let mut dedup = Dedup::new();
1010
1011 for i in 0..140 {
1012 dedup.insert(i);
1013 }
1014
1015 assert!(!dedup.missing_in_interval(0, 4));
1017 dedup.insert(160);
1018 assert!(!dedup.missing_in_interval(0, 4));
1019 assert!(!dedup.missing_in_interval(0, 140));
1020 assert!(dedup.missing_in_interval(0, 160));
1021 }
1022
1023 #[test]
1024 fn dedup_smallest_missing() {
1025 let mut dedup = Dedup::new();
1026
1027 dedup.insert(0);
1028 assert_eq!(dedup.smallest_missing_in_interval(0, 0), None);
1029
1030 dedup.insert(1);
1031 assert_eq!(dedup.smallest_missing_in_interval(0, 1), None);
1032
1033 dedup.insert(5);
1034 dedup.insert(7);
1035 assert_eq!(dedup.smallest_missing_in_interval(0, 7), Some(2));
1036 assert_eq!(dedup.smallest_missing_in_interval(5, 7), Some(6));
1037
1038 dedup.insert(2);
1039 assert_eq!(dedup.smallest_missing_in_interval(1, 7), Some(3));
1040
1041 dedup.insert(170);
1042 dedup.insert(172);
1043 dedup.insert(300);
1044 assert_eq!(dedup.smallest_missing_in_interval(170, 172), None);
1045
1046 dedup.insert(500);
1047 assert_eq!(dedup.smallest_missing_in_interval(0, 500), Some(372));
1048 assert_eq!(dedup.smallest_missing_in_interval(0, 373), Some(372));
1049 assert_eq!(dedup.smallest_missing_in_interval(0, 372), None);
1050 }
1051
1052 #[test]
1053 fn pending_acks_first_packet_is_not_considered_reordered() {
1054 let mut acks = PendingAcks::new();
1055 let mut dedup = Dedup::new();
1056 dedup.insert(0);
1057 acks.packet_received(Instant::now(), 0, true, &dedup);
1058 assert!(!acks.immediate_ack_required);
1059 }
1060
1061 #[test]
1062 fn pending_acks_after_immediate_ack_set() {
1063 let mut acks = PendingAcks::new();
1064 let mut dedup = Dedup::new();
1065
1066 dedup.insert(0);
1068 let now = Instant::now();
1069 acks.insert_one(0, now);
1070 acks.packet_received(now, 0, true, &dedup);
1071
1072 assert!(!acks.ranges.is_empty());
1074 assert!(!acks.can_send());
1075
1076 acks.set_immediate_ack_required();
1078 assert!(acks.can_send());
1079 }
1080
1081 #[test]
1082 fn pending_acks_ack_delay() {
1083 let mut acks = PendingAcks::new();
1084 let mut dedup = Dedup::new();
1085
1086 let t1 = Instant::now();
1087 let t2 = t1 + Duration::from_millis(2);
1088 let t3 = t2 + Duration::from_millis(5);
1089 assert_eq!(acks.ack_delay(t1), Duration::from_millis(0));
1090 assert_eq!(acks.ack_delay(t2), Duration::from_millis(0));
1091 assert_eq!(acks.ack_delay(t3), Duration::from_millis(0));
1092
1093 dedup.insert(0);
1095 acks.insert_one(0, t1);
1096 acks.packet_received(t1, 0, true, &dedup);
1097 assert_eq!(acks.ack_delay(t1), Duration::from_millis(0));
1098 assert_eq!(acks.ack_delay(t2), Duration::from_millis(2));
1099 assert_eq!(acks.ack_delay(t3), Duration::from_millis(7));
1100
1101 dedup.insert(3);
1103 acks.insert_one(3, t2);
1104 acks.packet_received(t2, 3, true, &dedup);
1105 assert_eq!(acks.ack_delay(t2), Duration::from_millis(0));
1106 assert_eq!(acks.ack_delay(t3), Duration::from_millis(5));
1107
1108 dedup.insert(2);
1110 acks.insert_one(2, t3);
1111 acks.packet_received(t3, 2, true, &dedup);
1112 assert_eq!(acks.ack_delay(t3), Duration::from_millis(5));
1113 }
1114
1115 #[test]
1116 fn sent_packet_size() {
1117 assert!(std::mem::size_of::<SentPacket>() <= 128);
1120 }
1121}