Skip to main content

quinn_proto/connection/
spaces.rs

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    /// Highest received packet number
23    pub(super) rx_packet: u64,
24
25    /// Data to send
26    pub(super) pending: Retransmits,
27    /// Packet numbers to acknowledge
28    pub(super) pending_acks: PendingAcks,
29
30    /// The packet number of the next packet that will be sent, if any. In the Data space, the
31    /// packet number stored here is sometimes skipped by [`PacketNumberFilter`] logic.
32    pub(super) next_packet_number: u64,
33    /// The largest packet number the remote peer acknowledged in an ACK frame.
34    pub(super) largest_acked_packet: Option<u64>,
35    pub(super) largest_acked_packet_sent: Instant,
36    /// The highest-numbered ACK-eliciting packet we've sent
37    pub(super) largest_ack_eliciting_sent: u64,
38    /// Number of packets in `sent_packets` with numbers above `largest_ack_eliciting_sent`
39    pub(super) unacked_non_ack_eliciting_tail: u64,
40    /// Transmitted but not acked
41    // We use a BTreeMap here so we can efficiently query by range on ACK and for loss detection
42    pub(super) sent_packets: BTreeMap<u64, SentPacket>,
43    /// Number of explicit congestion notification codepoints seen on incoming packets
44    pub(super) ecn_counters: frame::EcnCounts,
45    /// Recent ECN counters sent by the peer in ACK frames
46    ///
47    /// Updated (and inspected) whenever we receive an ACK with a new highest acked packet
48    /// number. Stored per-space to simplify verification, which would otherwise have difficulty
49    /// distinguishing between ECN bleaching and counts having been updated by a near-simultaneous
50    /// ACK already processed in another space.
51    pub(super) ecn_feedback: frame::EcnCounts,
52
53    /// Incoming cryptographic handshake stream
54    pub(super) crypto_stream: Assembler,
55    /// Current offset of outgoing cryptographic handshake stream
56    pub(super) crypto_offset: u64,
57
58    /// The time the most recently sent retransmittable packet was sent.
59    pub(super) time_of_last_ack_eliciting_packet: Option<Instant>,
60    /// The time at which the earliest sent packet in this space will be considered lost based on
61    /// exceeding the reordering window in time. Only set for packets numbered prior to a packet
62    /// that has been acknowledged.
63    pub(super) loss_time: Option<Instant>,
64    /// Number of tail loss probes to send
65    pub(super) loss_probes: u32,
66    pub(super) ping_pending: bool,
67    pub(super) immediate_ack_pending: bool,
68    /// Number of packets sent in the current key phase
69    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    /// Queue data for a tail loss probe (or anti-amplification deadlock prevention) packet
104    ///
105    /// Probes are sent similarly to normal packets when an expected ACK has not arrived. We never
106    /// deem a packet lost until we receive an ACK that should have included it, but if a trailing
107    /// run of packets (or their ACKs) are lost, this might not happen in a timely fashion. We send
108    /// probe packets to force an ACK, and exempt them from congestion control to prevent a deadlock
109    /// when the congestion window is filled with lost tail packets.
110    ///
111    /// We prefer to send new data, to make the most efficient use of bandwidth. If there's no data
112    /// waiting to be sent, then we retransmit in-flight data to reduce odds of loss. If there's no
113    /// in-flight data either, we're probably a client guarding against a handshake
114    /// anti-amplification deadlock and we just make something up.
115    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            // The probe should be ACKed without delay (should only be used in the Data space and
126            // when the peer supports the acknowledgement frequency extension)
127            self.immediate_ack_pending = true;
128        }
129
130        if !self.pending.is_empty(streams) {
131            // There's real data to send here, no need to make something up
132            return;
133        }
134
135        // Retransmit the data of the oldest in-flight packet
136        for packet in self.sent_packets.values_mut() {
137            if !packet.retransmits.is_empty(streams) {
138                // Remove retransmitted data from the old packet so we don't end up retransmitting
139                // it *again* even if the copy we're sending now gets acknowledged.
140                self.pending |= mem::take(&mut packet.retransmits);
141                return;
142            }
143        }
144
145        // Nothing new to send and nothing to retransmit, so fall back on a ping. This should only
146        // happen in rare cases during the handshake when the server becomes blocked by
147        // anti-amplification.
148        if !self.immediate_ack_pending {
149            self.ping_pending = true;
150        }
151    }
152
153    /// Get the next outgoing packet number in this space
154    ///
155    /// In the Data space, the connection's [`PacketNumberFilter`] must be used rather than calling
156    /// this directly.
157    pub(super) fn get_tx_number(&mut self) -> u64 {
158        // TODO: Handle packet number overflow gracefully
159        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    /// Verifies sanity of an ECN block and returns whether congestion was encountered.
175    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        // If total_increase > newly_acked (which happens when ACKs are lost), this is required by
200        // the draft so that long-term drift does not occur. If =, then the only question is whether
201        // to count CE packets as CE or ECT0. Recording them as CE is more consistent and keeps the
202        // congestion check obvious.
203        self.ecn_feedback = ecn;
204        Ok(ce_increase != 0)
205    }
206
207    /// Stop tracking sent packet `number`, and return what we knew about it
208    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    /// May return a packet that should be forgotten
218    pub(super) fn sent(&mut self, number: u64, packet: SentPacket) -> Option<SentPacket> {
219        // Retain state for at most this many non-ACK-eliciting packets sent after the most recently
220        // sent ACK-eliciting packet. We're never guaranteed to receive an ACK for those, and we
221        // can't judge them as lost without an ACK, so to limit memory in applications which receive
222        // packets but don't send ACK-eliciting data for long periods use we must eventually start
223        // forgetting about them, although it might also be reasonable to just kill the connection
224        // due to weird peer behavior.
225        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            // Per https://www.rfc-editor.org/rfc/rfc9000.html#name-frames-and-frame-types,
242            // non-ACK-eliciting packets must only contain PADDING, ACK, and CONNECTION_CLOSE
243            // frames, which require no special handling on ACK or loss beyond removal from
244            // in-flight counters if padded.
245            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    /// Whether any congestion-controlled packets in this space are not yet acknowledged or lost
260    pub(super) fn has_in_flight(&self) -> bool {
261        // The number of non-congestion-controlled (i.e. size == 0) packets in flight at a time
262        // should be small, since otherwise congestion control wouldn't be effective. Therefore,
263        // this shouldn't need to visit many packets before finishing one way or another.
264        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/// Represents one or more packets subject to retransmission
282#[derive(Debug, Clone)]
283pub(super) struct SentPacket {
284    /// [`PathData::generation`](super::PathData::generation) of the path on which this packet was sent
285    pub(super) path_generation: u64,
286    /// The time the packet was sent.
287    pub(super) time_sent: Instant,
288    /// The number of bytes sent in the packet, not including UDP or IP overhead, but including QUIC
289    /// framing overhead. Zero if this packet is not counted towards congestion control, i.e. not an
290    /// "in flight" packet.
291    pub(super) size: u16,
292    /// Whether an acknowledgement is expected directly in response to this packet.
293    pub(super) ack_eliciting: bool,
294    /// The largest packet number acknowledged by this packet
295    pub(super) largest_acked: Option<u64>,
296    /// Data which needs to be retransmitted in case the packet is lost.
297    /// The data is boxed to minimize `SentPacket` size for the typical case of
298    /// packets only containing ACKs and STREAM frames.
299    pub(super) retransmits: ThinRetransmits,
300    /// Metadata for stream frames in a packet
301    ///
302    /// The actual application data is stored with the stream state.
303    pub(super) stream_frames: frame::StreamMetaVec,
304}
305
306/// Retransmittable data queue
307#[allow(unreachable_pub)] // fuzzing only
308#[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    /// For each enqueued NEW_TOKEN frame, a copy of the path's remote address
323    ///
324    /// There are 2 reasons this is unusual:
325    ///
326    /// - If the path changes, NEW_TOKEN frames bound for the old path are not retransmitted on the
327    ///   new path. That is why this field stores the remote address: so that ones for old paths
328    ///   can be filtered out.
329    /// - If a token is lost, a new randomly generated token is re-transmitted, rather than the
330    ///   original. This is so that if both transmissions are received, the client won't risk
331    ///   sending the same token twice. That is why this field does _not_ store any actual token.
332    ///
333    /// It is true that a QUIC endpoint will only want to effectively have NEW_TOKEN frames
334    /// enqueued for its current path at a given point in time. Based on that, we could conceivably
335    /// change this from a vector to an `Option<(SocketAddr, usize)>` or just a `usize` or
336    /// something. However, due to the architecture of Quinn, it is considerably simpler to not do
337    /// that; consider what such a change would mean for implementing `BitOrAssign` on Self.
338    pub(super) new_tokens: Vec<SocketAddr>,
339}
340
341impl Retransmits {
342    pub(super) fn retire_cids(&mut self, cids: Range<u64>) -> Result<(), TransportError> {
343        // We don't bother counting in-flight frames because those are bounded by congestion control.
344        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    /// Ensure `pending_retired` cannot grow without bound
378    ///
379    /// Limit is somewhat arbitrary but very permissive.
380    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        // We reduce in-stream head-of-line blocking by queueing retransmits before other data for
386        // STREAM and CRYPTO frames.
387        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/// A variant of `Retransmits` which only allocates storage when required
429#[derive(Debug, Default, Clone)]
430pub(super) struct ThinRetransmits {
431    retransmits: Option<Box<Retransmits>>,
432}
433
434impl ThinRetransmits {
435    /// Returns `true` if no retransmits are necessary
436    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    /// Returns a reference to the retransmits stored in this box
444    pub(super) fn get(&self) -> Option<&Retransmits> {
445        self.retransmits.as_deref()
446    }
447
448    /// Returns a mutable reference to the stored retransmits
449    ///
450    /// This function will allocate a backing storage if required.
451    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
459/// RFC4303-style sliding window packet number deduplicator.
460///
461/// A contiguous bitfield, where each bit corresponds to a packet number and the rightmost bit is
462/// always set. A set bit represents a packet that has been successfully authenticated. Bits left of
463/// the window are assumed to be set.
464///
465/// ```text
466/// ...xxxxxxxxx 1 0
467///     ^        ^ ^
468/// window highest next
469/// ```
470pub(super) struct Dedup {
471    window: Window,
472    /// Lowest packet number higher than all yet authenticated.
473    next: u64,
474}
475
476/// Inner bitfield type.
477///
478/// Because QUIC never reuses packet numbers, this only needs to be large enough to deal with
479/// packets that are reordered but still delivered in a timely manner.
480type Window = u128;
481
482/// Number of packets tracked by `Dedup`.
483const WINDOW_SIZE: u64 = 1 + mem::size_of::<Window>() as u64 * 8;
484
485impl Dedup {
486    /// Construct an empty window positioned at the start.
487    pub(super) fn new() -> Self {
488        Self { window: 0, next: 0 }
489    }
490
491    /// Highest packet number authenticated.
492    fn highest(&self) -> u64 {
493        self.next - 1
494    }
495
496    /// Record a newly authenticated packet number.
497    ///
498    /// Returns whether the packet might be a duplicate.
499    pub(super) fn insert(&mut self, packet: u64) -> bool {
500        if let Some(diff) = packet.checked_sub(self.next) {
501            // Right of window
502            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            // Within window
509            if let Some(bit) = (self.highest() - packet).checked_sub(1) {
510                // < highest
511                let mask = 1 << bit;
512                let duplicate = self.window & mask != 0;
513                self.window |= mask;
514                duplicate
515            } else {
516                // == highest
517                true
518            }
519        } else {
520            // Left of window
521            true
522        }
523    }
524
525    /// Returns the packet number of the smallest packet missing between the provided interval
526    ///
527    /// If there are no missing packets, returns `None`
528    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        // Since we already know the packets at the boundaries have been received, we only need to
534        // check those in between them (this removes the necessity of extra logic to deal with the
535        // highest packet, which is stored outside the bitfield)
536        let lower_bound = lower_bound + 1;
537        let upper_bound = upper_bound.saturating_sub(1);
538
539        // Note: the offsets are counted from the right
540        // The highest packet is not included in the bitfield, so we subtract 1 to account for that
541        let start_offset = (self.highest() - upper_bound).max(1) - 1;
542        if start_offset >= BITFIELD_SIZE {
543            // The start offset is outside of the window. All packets outside of the window are
544            // considered to be received.
545            return None;
546        }
547
548        let end_offset_exclusive = self.highest().saturating_sub(lower_bound);
549
550        // The range is clamped at the edge of the window, because any earlier packets are
551        // considered to be received
552        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        // Ensure the shift is within bounds (we already know start_offset < BITFIELD_SIZE,
560        // because of the early return)
561        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    /// Returns true if there are any missing packets between the provided interval
579    ///
580    /// The provided packet numbers must have been received before calling this function
581    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/// Indicates which data is available for sending
588#[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    /// Returns that no data is available for sending
596    pub(super) fn empty() -> Self {
597        Self {
598            acks: false,
599            other: false,
600        }
601    }
602
603    /// Whether no data is sendable
604    pub(super) fn is_empty(&self) -> bool {
605        !self.acks && !self.other
606    }
607}
608
609#[derive(Debug)]
610pub(super) struct PendingAcks {
611    /// Whether we should send an ACK immediately, even if that means sending an ACK-only packet
612    ///
613    /// When `immediate_ack_required` is false, the normal behavior is to send ACK frames only when
614    /// there is other data to send, or when the `MaxAckDelay` timer expires.
615    immediate_ack_required: bool,
616    /// The number of ack-eliciting packets received since the last ACK frame was sent
617    ///
618    /// Once the count _exceeds_ `ack_eliciting_threshold`, an immediate ACK is required
619    ack_eliciting_since_last_ack_sent: u64,
620    non_ack_eliciting_since_last_ack_sent: u64,
621    ack_eliciting_threshold: u64,
622    /// The reordering threshold, controlling how we respond to out-of-order ack-eliciting packets
623    ///
624    /// Different values enable different behavior:
625    ///
626    /// * `0`: no special action is taken
627    /// * `1`: an ACK is immediately sent if it is out-of-order according to RFC 9000
628    /// * `>1`: an ACK is immediately sent if it is out-of-order according to the ACK frequency draft
629    reordering_threshold: u64,
630    /// The earliest ack-eliciting packet since the last ACK was sent, used to calculate the moment
631    /// upon which `max_ack_delay` elapses
632    earliest_ack_eliciting_since_last_ack_sent: Option<Instant>,
633    /// The packet number ranges of ack-eliciting packets the peer hasn't confirmed receipt of ACKs
634    /// for
635    ranges: ArrayRangeSet,
636    /// The packet with the largest packet number, and the time upon which it was received (used to
637    /// calculate ACK delay in [`PendingAcks::ack_delay`])
638    largest_packet: Option<(u64, Instant)>,
639    /// The ack-eliciting packet we have received with the largest packet number
640    largest_ack_eliciting_packet: Option<u64>,
641    /// The largest acknowledged packet number sent in an ACK frame
642    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    /// Whether any ACK frames can be sent even if doing so requires a dedicated packet
680    pub(super) fn can_send(&self) -> bool {
681        self.immediate_ack_required && !self.ranges.is_empty()
682    }
683
684    /// Whether any ACK frames can be sent in data-initiated packets
685    pub(super) fn can_send_with_other_frames(&self) -> bool {
686        !self.ranges.is_empty()
687    }
688
689    /// Returns the delay since the packet with the largest packet number was received
690    pub(super) fn ack_delay(&self, now: Instant) -> Duration {
691        self.largest_packet
692            .map_or(Duration::default(), |(_, received)| now - received)
693    }
694
695    /// Handle receipt of a new packet
696    ///
697    /// Returns true if the max ack delay timer should be armed
698    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        // Track largest ack-eliciting packet
713        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        // Handle ack_eliciting_threshold
719        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        // Handle out-of-order packets
724        self.immediate_ack_required |=
725            self.is_out_of_order(packet_number, prev_largest_ack_eliciting, dedup);
726
727        // Arm max_ack_delay timer if necessary
728        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                // From https://www.rfc-editor.org/rfc/rfc9000#section-13.2.1-7
746                packet_number < prev_largest_ack_eliciting
747                    || dedup.missing_in_interval(prev_largest_ack_eliciting, packet_number)
748            }
749            _ => {
750                // From acknowledgement frequency draft, section 6.1: send an ACK immediately if
751                // doing so would cause the sender to detect a new packet loss
752                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                // The largest packet number that could be declared lost without a new ACK being
761                // sent
762                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    /// Should be called whenever ACKs have been sent
774    ///
775    /// This will suppress sending further ACKs until additional ACK eliciting frames arrive
776    pub(super) fn acks_sent(&mut self) {
777        // It is possible (though unlikely) that the ACKs we just sent do not cover all the
778        // ACK-eliciting packets we have received (e.g. if there is not enough room in the packet to
779        // fit all the ranges). To keep things simple, however, we assume they do. If there are
780        // indeed some ACKs that weren't covered, the packets might be ACKed later anyway, because
781        // they are still contained in `self.ranges`. If we somehow fail to send the ACKs at a later
782        // moment, the peer will assume the packets got lost and will retransmit their frames in a
783        // new packet, which is suboptimal, because we already received them. Our assumption here is
784        // that simplicity results in code that is more performant, even in the presence of
785        // occasional redundant retransmits.
786        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    /// Insert one packet that needs to be acknowledged
794    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    /// Remove ACKs of packets numbered at or below `max` from the set of pending ACKs
807    pub(super) fn subtract_below(&mut self, max: u64) {
808        self.ranges.remove(0..(max + 1));
809    }
810
811    /// Returns the set of currently pending ACK ranges
812    pub(super) fn ranges(&self) -> &ArrayRangeSet {
813        &self.ranges
814    }
815
816    /// Queue an ACK if a significant number of non-ACK-eliciting packets have not yet been
817    /// acknowledged
818    ///
819    /// Should be called immediately before a non-probing packet is composed, when we've already
820    /// committed to sending a packet regardless.
821    pub(super) fn maybe_ack_non_eliciting(&mut self) {
822        // If we're going to send a packet anyway, and we've received a significant number of
823        // non-ACK-eliciting packets, then include an ACK to help the peer perform timely loss
824        // detection even if they're not sending any ACK-eliciting packets themselves. Exact
825        // threshold chosen somewhat arbitrarily.
826        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
833/// Helper for mitigating [optimistic ACK attacks]
834///
835/// A malicious peer could prompt the local application to begin a large data transfer, and then
836/// send ACKs without first waiting for data to be received. This could defeat congestion control,
837/// allowing the connection to consume disproportionate resources. We therefore occasionally skip
838/// packet numbers, and classify any ACK referencing a skipped packet number as a transport error.
839///
840/// Skipped packet numbers occur only in the application data space (where costly transfers might
841/// take place) and are distributed exponentially to reflect the reduced likelihood and impact of
842/// bad behavior from a peer that has been well-behaved for an extended period.
843///
844/// ACKs for packet numbers that have not yet been allocated are also a transport error, but an
845/// attacker with knowledge of the congestion control algorithm in use could time falsified ACKs to
846/// arrive after the packets they reference are sent.
847///
848/// [optimistic ACK attacks]: https://www.rfc-editor.org/rfc/rfc9000.html#name-optimistic-ack-attack
849pub(super) struct PacketNumberFilter {
850    /// Next outgoing packet number to skip
851    next_skipped_packet_number: u64,
852    /// Most recently skipped packet number
853    prev_skipped_packet_number: Option<u64>,
854    /// Next packet number to skip is randomly selected from 2^n..2^n+1
855    exponent: u32,
856}
857
858impl PacketNumberFilter {
859    pub(super) fn new(rng: &mut (impl Rng + ?Sized)) -> Self {
860        // First skipped PN is in 0..64
861        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        // Skip this packet number, and choose the next one to skip
898        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
923/// Ensures we can always fit all our ACKs in a single minimum-MTU packet with room to spare
924const 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        // 0 and 4 are outside of the window
1016        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        // Receive ack-eliciting packet
1067        dedup.insert(0);
1068        let now = Instant::now();
1069        acks.insert_one(0, now);
1070        acks.packet_received(now, 0, true, &dedup);
1071
1072        // Sanity check
1073        assert!(!acks.ranges.is_empty());
1074        assert!(!acks.can_send());
1075
1076        // Can send ACK after max_ack_delay exceeded
1077        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        // In-order packet
1094        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        // Out of order (higher than expected)
1102        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        // Out of order (lower than expected, so previous instant is kept)
1109        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        // The tracking state of sent packets should be minimal, and not grow
1118        // over time.
1119        assert!(std::mem::size_of::<SentPacket>() <= 128);
1120    }
1121}