quiche/
path.rs

1// Copyright (C) 2022, Cloudflare, Inc.
2// All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8//     * Redistributions of source code must retain the above copyright notice,
9//       this list of conditions and the following disclaimer.
10//
11//     * Redistributions in binary form must reproduce the above copyright
12//       notice, this list of conditions and the following disclaimer in the
13//       documentation and/or other materials provided with the distribution.
14//
15// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
16// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
17// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
19// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27use std::collections::BTreeMap;
28use std::collections::VecDeque;
29
30use std::net::SocketAddr;
31
32use std::time::Duration;
33use std::time::Instant;
34
35use smallvec::SmallVec;
36
37use slab::Slab;
38
39use crate::Config;
40use crate::Error;
41use crate::Result;
42use crate::StartupExit;
43
44use crate::pmtud;
45use crate::recovery;
46use crate::recovery::Bandwidth;
47use crate::recovery::HandshakeStatus;
48use crate::recovery::OnLossDetectionTimeoutOutcome;
49use crate::recovery::RecoveryOps;
50
51/// The different states of the path validation.
52#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
53pub enum PathState {
54    /// The path failed its validation.
55    Failed,
56
57    /// The path exists, but no path validation has been performed.
58    Unknown,
59
60    /// The path is under validation.
61    Validating,
62
63    /// The remote address has been validated, but not the path MTU.
64    ValidatingMTU,
65
66    /// The path has been validated.
67    Validated,
68}
69
70impl PathState {
71    #[cfg(feature = "ffi")]
72    pub fn to_c(self) -> libc::ssize_t {
73        match self {
74            PathState::Failed => -1,
75            PathState::Unknown => 0,
76            PathState::Validating => 1,
77            PathState::ValidatingMTU => 2,
78            PathState::Validated => 3,
79        }
80    }
81}
82
83/// A path-specific event.
84#[derive(Clone, Debug, PartialEq, Eq)]
85pub enum PathEvent {
86    /// A new network path (local address, peer address) has been seen on a
87    /// received packet. Note that this event is only triggered for servers, as
88    /// the client is responsible from initiating new paths. The application may
89    /// then probe this new path, if desired.
90    New(SocketAddr, SocketAddr),
91
92    /// The related network path between local `SocketAddr` and peer
93    /// `SocketAddr` has been validated.
94    Validated(SocketAddr, SocketAddr),
95
96    /// The related network path between local `SocketAddr` and peer
97    /// `SocketAddr` failed to be validated. This network path will not be used
98    /// anymore, unless the application requests probing this path again.
99    FailedValidation(SocketAddr, SocketAddr),
100
101    /// The related network path between local `SocketAddr` and peer
102    /// `SocketAddr` has been closed and is now unusable on this connection.
103    Closed(SocketAddr, SocketAddr),
104
105    /// The stack observes that the Source Connection ID with the given sequence
106    /// number, initially used by the peer over the first pair of `SocketAddr`s,
107    /// is now reused over the second pair of `SocketAddr`s.
108    ReusedSourceConnectionId(
109        u64,
110        (SocketAddr, SocketAddr),
111        (SocketAddr, SocketAddr),
112    ),
113
114    /// The connection observed that the peer migrated over the network path
115    /// denoted by the pair of `SocketAddr`, i.e., non-probing packets have been
116    /// received on this network path. This is a server side only event.
117    ///
118    /// Note that this event is only raised if the path has been validated.
119    PeerMigrated(SocketAddr, SocketAddr),
120}
121
122/// A network path on which QUIC packets can be sent.
123#[derive(Debug)]
124pub struct Path {
125    /// The local address.
126    local_addr: SocketAddr,
127
128    /// The remote address.
129    peer_addr: SocketAddr,
130
131    /// Source CID sequence number used over that path.
132    pub active_scid_seq: Option<u64>,
133
134    /// Destination CID sequence number used over that path.
135    pub active_dcid_seq: Option<u64>,
136
137    /// The current validation state of the path.
138    state: PathState,
139
140    /// Is this path used to send non-probing packets.
141    active: bool,
142
143    /// Loss recovery and congestion control state.
144    pub recovery: recovery::Recovery,
145
146    /// Path MTU discovery state. None if PMTUD is disabled on the path.
147    pub pmtud: Option<pmtud::Pmtud>,
148
149    /// Pending challenge data with the size of the packet containing them and
150    /// when they were sent.
151    in_flight_challenges: VecDeque<([u8; 8], usize, Instant)>,
152
153    /// The maximum challenge size that got acknowledged.
154    max_challenge_size: usize,
155
156    /// Number of consecutive (spaced by at least 1 RTT) probing packets lost.
157    probing_lost: usize,
158
159    /// Last instant when a probing packet got lost.
160    last_probe_lost_time: Option<Instant>,
161
162    /// Received challenge data.
163    received_challenges: VecDeque<[u8; 8]>,
164
165    /// Max length of received challenges queue.
166    received_challenges_max_len: usize,
167
168    /// Number of packets sent on this path.
169    pub sent_count: usize,
170
171    /// Number of packets received on this path.
172    pub recv_count: usize,
173
174    /// Total number of packets sent with data retransmitted from this path.
175    pub retrans_count: usize,
176
177    /// Total number of times PTO (probe timeout) fired.
178    ///
179    /// Loss usually happens in a burst so the number of packets lost will
180    /// depend on the volume of inflight packets at the time of loss (which
181    /// can be arbitrary). PTO count measures the number of loss events and
182    /// provides a normalized loss metric.
183    pub total_pto_count: usize,
184
185    /// Number of DATAGRAM frames sent on this path.
186    pub dgram_sent_count: usize,
187
188    /// Number of DATAGRAM frames received on this path.
189    pub dgram_recv_count: usize,
190
191    /// Total number of sent bytes over this path.
192    pub sent_bytes: u64,
193
194    /// Total number of bytes received over this path.
195    pub recv_bytes: u64,
196
197    /// Total number of bytes retransmitted from this path.
198    /// This counts only STREAM and CRYPTO data.
199    pub stream_retrans_bytes: u64,
200
201    /// Total number of bytes the server can send before the peer's address
202    /// is verified.
203    pub max_send_bytes: usize,
204
205    /// Whether the peer's address has been verified.
206    pub verified_peer_address: bool,
207
208    /// Whether the peer has verified our address.
209    pub peer_verified_local_address: bool,
210
211    /// Does it requires sending PATH_CHALLENGE?
212    challenge_requested: bool,
213
214    /// Whether the failure of this path was notified.
215    failure_notified: bool,
216
217    /// Whether the connection tries to migrate to this path, but it still needs
218    /// to be validated.
219    migrating: bool,
220
221    /// Whether or not we should force eliciting of an ACK (e.g. via PING frame)
222    pub needs_ack_eliciting: bool,
223}
224
225impl Path {
226    /// Create a new Path instance with the provided addresses, the remaining of
227    /// the fields being set to their default value.
228    pub fn new(
229        local_addr: SocketAddr, peer_addr: SocketAddr,
230        recovery_config: &recovery::RecoveryConfig,
231        path_challenge_recv_max_queue_len: usize, is_initial: bool,
232        config: Option<&Config>,
233    ) -> Self {
234        let (state, active_scid_seq, active_dcid_seq) = if is_initial {
235            (PathState::Validated, Some(0), Some(0))
236        } else {
237            (PathState::Unknown, None, None)
238        };
239
240        let pmtud = config.and_then(|c| {
241            if c.pmtud {
242                let maximum_supported_mtu: usize = std::cmp::min(
243                    // if the max_udp_payload_size doesn't fit into a usize, then
244                    // max_send_udp_payload_size must be smaller so use that
245                    c.local_transport_params
246                        .max_udp_payload_size
247                        .try_into()
248                        .unwrap_or(c.max_send_udp_payload_size),
249                    c.max_send_udp_payload_size,
250                );
251                Some(pmtud::Pmtud::new(maximum_supported_mtu))
252            } else {
253                None
254            }
255        });
256
257        Self {
258            local_addr,
259            peer_addr,
260            active_scid_seq,
261            active_dcid_seq,
262            state,
263            active: false,
264            recovery: recovery::Recovery::new_with_config(recovery_config),
265            pmtud,
266            in_flight_challenges: VecDeque::new(),
267            max_challenge_size: 0,
268            probing_lost: 0,
269            last_probe_lost_time: None,
270            received_challenges: VecDeque::with_capacity(
271                path_challenge_recv_max_queue_len,
272            ),
273            received_challenges_max_len: path_challenge_recv_max_queue_len,
274            sent_count: 0,
275            recv_count: 0,
276            retrans_count: 0,
277            total_pto_count: 0,
278            dgram_sent_count: 0,
279            dgram_recv_count: 0,
280            sent_bytes: 0,
281            recv_bytes: 0,
282            stream_retrans_bytes: 0,
283            max_send_bytes: 0,
284            verified_peer_address: false,
285            peer_verified_local_address: false,
286            challenge_requested: false,
287            failure_notified: false,
288            migrating: false,
289            needs_ack_eliciting: false,
290        }
291    }
292
293    /// Returns the local address on which this path operates.
294    #[inline]
295    pub fn local_addr(&self) -> SocketAddr {
296        self.local_addr
297    }
298
299    /// Returns the peer address on which this path operates.
300    #[inline]
301    pub fn peer_addr(&self) -> SocketAddr {
302        self.peer_addr
303    }
304
305    /// Returns whether the path is working (i.e., not failed).
306    #[inline]
307    fn working(&self) -> bool {
308        self.state > PathState::Failed
309    }
310
311    /// Returns whether the path is active.
312    #[inline]
313    pub fn active(&self) -> bool {
314        self.active && self.working() && self.active_dcid_seq.is_some()
315    }
316
317    /// Returns whether the path can be used to send non-probing packets.
318    #[inline]
319    pub fn usable(&self) -> bool {
320        self.active() ||
321            (self.state == PathState::Validated &&
322                self.active_dcid_seq.is_some())
323    }
324
325    /// Returns whether the path is unused.
326    #[inline]
327    fn unused(&self) -> bool {
328        // FIXME: we should check that there is nothing in the sent queue.
329        !self.active() && self.active_dcid_seq.is_none()
330    }
331
332    /// Returns whether the path requires sending a probing packet.
333    #[inline]
334    pub fn probing_required(&self) -> bool {
335        !self.received_challenges.is_empty() || self.validation_requested()
336    }
337
338    /// Promotes the path to the provided state only if the new state is greater
339    /// than the current one.
340    fn promote_to(&mut self, state: PathState) {
341        if self.state < state {
342            self.state = state;
343        }
344    }
345
346    /// Returns whether the path is validated.
347    #[inline]
348    pub fn validated(&self) -> bool {
349        self.state == PathState::Validated
350    }
351
352    /// Returns whether this path failed its validation.
353    #[inline]
354    fn validation_failed(&self) -> bool {
355        self.state == PathState::Failed
356    }
357
358    // Returns whether this path is under path validation process.
359    #[inline]
360    pub fn under_validation(&self) -> bool {
361        matches!(self.state, PathState::Validating | PathState::ValidatingMTU)
362    }
363
364    /// Requests path validation.
365    #[inline]
366    pub fn request_validation(&mut self) {
367        self.challenge_requested = true;
368    }
369
370    /// Returns whether a validation is requested.
371    #[inline]
372    pub fn validation_requested(&self) -> bool {
373        self.challenge_requested
374    }
375
376    pub fn should_send_pmtu_probe(
377        &mut self, hs_confirmed: bool, hs_done: bool, out_len: usize,
378        is_closing: bool, frames_empty: bool,
379    ) -> bool {
380        let Some(pmtud) = self.pmtud.as_mut() else {
381            return false;
382        };
383
384        (hs_confirmed && hs_done) &&
385            self.recovery.cwnd_available() > pmtud.get_probe_size() &&
386            out_len >= pmtud.get_probe_size() &&
387            pmtud.should_probe() &&
388            !is_closing &&
389            frames_empty
390    }
391
392    pub fn on_challenge_sent(&mut self) {
393        self.promote_to(PathState::Validating);
394        self.challenge_requested = false;
395    }
396
397    /// Handles the sending of PATH_CHALLENGE.
398    pub fn add_challenge_sent(
399        &mut self, data: [u8; 8], pkt_size: usize, sent_time: Instant,
400    ) {
401        self.on_challenge_sent();
402        self.in_flight_challenges
403            .push_back((data, pkt_size, sent_time));
404    }
405
406    pub fn on_challenge_received(&mut self, data: [u8; 8]) {
407        // Discard challenges that would cause us to queue more than we want.
408        if self.received_challenges.len() == self.received_challenges_max_len {
409            return;
410        }
411
412        self.received_challenges.push_back(data);
413        self.peer_verified_local_address = true;
414    }
415
416    pub fn has_pending_challenge(&self, data: [u8; 8]) -> bool {
417        self.in_flight_challenges.iter().any(|(d, ..)| *d == data)
418    }
419
420    /// Returns whether the path is now validated.
421    pub fn on_response_received(&mut self, data: [u8; 8]) -> bool {
422        self.verified_peer_address = true;
423        self.probing_lost = 0;
424
425        let mut challenge_size = 0;
426        self.in_flight_challenges.retain(|(d, s, _)| {
427            if *d == data {
428                challenge_size = *s;
429                false
430            } else {
431                true
432            }
433        });
434
435        // The 4-tuple is reachable, but we didn't check Path MTU yet.
436        self.promote_to(PathState::ValidatingMTU);
437
438        self.max_challenge_size =
439            std::cmp::max(self.max_challenge_size, challenge_size);
440
441        if self.state == PathState::ValidatingMTU {
442            if self.max_challenge_size >= crate::MIN_CLIENT_INITIAL_LEN {
443                // Path MTU is sufficient for QUIC traffic.
444                self.promote_to(PathState::Validated);
445                return true;
446            }
447
448            // If the MTU was not validated, probe again.
449            self.request_validation();
450        }
451
452        false
453    }
454
455    fn on_failed_validation(&mut self) {
456        self.state = PathState::Failed;
457        self.active = false;
458    }
459
460    #[inline]
461    pub fn pop_received_challenge(&mut self) -> Option<[u8; 8]> {
462        self.received_challenges.pop_front()
463    }
464
465    pub fn on_loss_detection_timeout(
466        &mut self, handshake_status: HandshakeStatus, now: Instant,
467        is_server: bool, trace_id: &str,
468    ) -> OnLossDetectionTimeoutOutcome {
469        let outcome = self.recovery.on_loss_detection_timeout(
470            handshake_status,
471            now,
472            trace_id,
473        );
474
475        let mut lost_probe_time = None;
476        self.in_flight_challenges.retain(|(_, _, sent_time)| {
477            if *sent_time <= now {
478                if lost_probe_time.is_none() {
479                    lost_probe_time = Some(*sent_time);
480                }
481                false
482            } else {
483                true
484            }
485        });
486
487        // If we lost probing packets, check if the path failed
488        // validation.
489        if let Some(lost_probe_time) = lost_probe_time {
490            self.last_probe_lost_time = match self.last_probe_lost_time {
491                Some(last) => {
492                    // Count a loss if at least 1-RTT happened.
493                    if lost_probe_time - last >= self.recovery.rtt() {
494                        self.probing_lost += 1;
495                        Some(lost_probe_time)
496                    } else {
497                        Some(last)
498                    }
499                },
500                None => {
501                    self.probing_lost += 1;
502                    Some(lost_probe_time)
503                },
504            };
505            // As a server, if requesting a challenge is not
506            // possible due to the amplification attack, declare the
507            // validation as failed.
508            if self.probing_lost >= crate::MAX_PROBING_TIMEOUTS ||
509                (is_server && self.max_send_bytes < crate::MIN_PROBING_SIZE)
510            {
511                self.on_failed_validation();
512            } else {
513                self.request_validation();
514            }
515        }
516
517        // Track PTO timeout event
518        self.total_pto_count += 1;
519
520        outcome
521    }
522
523    pub fn reinit_recovery(
524        &mut self, recovery_config: &recovery::RecoveryConfig,
525    ) {
526        self.recovery = recovery::Recovery::new_with_config(recovery_config)
527    }
528
529    pub fn stats(&self) -> PathStats {
530        let pmtu = match self.pmtud.as_ref().map(|p| p.get_current_mtu()) {
531            Some(v) => v,
532
533            None => self.recovery.max_datagram_size(),
534        };
535
536        PathStats {
537            local_addr: self.local_addr,
538            peer_addr: self.peer_addr,
539            validation_state: self.state,
540            active: self.active,
541            recv: self.recv_count,
542            sent: self.sent_count,
543            lost: self.recovery.lost_count(),
544            retrans: self.retrans_count,
545            total_pto_count: self.total_pto_count,
546            dgram_recv: self.dgram_recv_count,
547            dgram_sent: self.dgram_sent_count,
548            rtt: self.recovery.rtt(),
549            min_rtt: self.recovery.min_rtt(),
550            max_rtt: self.recovery.max_rtt(),
551            rttvar: self.recovery.rttvar(),
552            cwnd: self.recovery.cwnd(),
553            sent_bytes: self.sent_bytes,
554            recv_bytes: self.recv_bytes,
555            lost_bytes: self.recovery.bytes_lost(),
556            stream_retrans_bytes: self.stream_retrans_bytes,
557            pmtu,
558            delivery_rate: self.recovery.delivery_rate().to_bytes_per_second(),
559            max_bandwidth: self
560                .recovery
561                .max_bandwidth()
562                .map(Bandwidth::to_bytes_per_second),
563            startup_exit: self.recovery.startup_exit(),
564        }
565    }
566
567    pub fn bytes_in_flight_duration(&self) -> Duration {
568        self.recovery.bytes_in_flight_duration()
569    }
570}
571
572/// An iterator over SocketAddr.
573#[derive(Default)]
574pub struct SocketAddrIter {
575    pub(crate) sockaddrs: SmallVec<[SocketAddr; 8]>,
576    pub(crate) index: usize,
577}
578
579impl Iterator for SocketAddrIter {
580    type Item = SocketAddr;
581
582    #[inline]
583    fn next(&mut self) -> Option<Self::Item> {
584        let v = self.sockaddrs.get(self.index)?;
585        self.index += 1;
586        Some(*v)
587    }
588}
589
590impl ExactSizeIterator for SocketAddrIter {
591    #[inline]
592    fn len(&self) -> usize {
593        self.sockaddrs.len() - self.index
594    }
595}
596
597/// All path-related information.
598pub struct PathMap {
599    /// The paths of the connection. Each of them has an internal identifier
600    /// that is used by `addrs_to_paths` and `ConnectionEntry`.
601    paths: Slab<Path>,
602
603    /// The maximum number of concurrent paths allowed.
604    max_concurrent_paths: usize,
605
606    /// The mapping from the (local `SocketAddr`, peer `SocketAddr`) to the
607    /// `Path` structure identifier.
608    addrs_to_paths: BTreeMap<(SocketAddr, SocketAddr), usize>,
609
610    /// Path-specific events to be notified to the application.
611    events: VecDeque<PathEvent>,
612
613    /// Whether this manager serves a connection as a server.
614    is_server: bool,
615}
616
617impl PathMap {
618    /// Creates a new `PathMap` with the initial provided `path` and a
619    /// capacity limit.
620    pub fn new(
621        mut initial_path: Path, max_concurrent_paths: usize, is_server: bool,
622    ) -> Self {
623        let mut paths = Slab::with_capacity(1); // most connections only have one path
624        let mut addrs_to_paths = BTreeMap::new();
625
626        let local_addr = initial_path.local_addr;
627        let peer_addr = initial_path.peer_addr;
628
629        // As it is the first path, it is active by default.
630        initial_path.active = true;
631
632        let active_path_id = paths.insert(initial_path);
633        addrs_to_paths.insert((local_addr, peer_addr), active_path_id);
634
635        Self {
636            paths,
637            max_concurrent_paths,
638            addrs_to_paths,
639            events: VecDeque::new(),
640            is_server,
641        }
642    }
643
644    /// Gets an immutable reference to the path identified by `path_id`. If the
645    /// provided `path_id` does not identify any current `Path`, returns an
646    /// [`InvalidState`].
647    ///
648    /// [`InvalidState`]: enum.Error.html#variant.InvalidState
649    #[inline]
650    pub fn get(&self, path_id: usize) -> Result<&Path> {
651        self.paths.get(path_id).ok_or(Error::InvalidState)
652    }
653
654    /// Gets a mutable reference to the path identified by `path_id`. If the
655    /// provided `path_id` does not identify any current `Path`, returns an
656    /// [`InvalidState`].
657    ///
658    /// [`InvalidState`]: enum.Error.html#variant.InvalidState
659    #[inline]
660    pub fn get_mut(&mut self, path_id: usize) -> Result<&mut Path> {
661        self.paths.get_mut(path_id).ok_or(Error::InvalidState)
662    }
663
664    #[inline]
665    /// Gets an immutable reference to the active path with the value of the
666    /// lowest identifier. If there is no active path, returns `None`.
667    pub fn get_active_with_pid(&self) -> Option<(usize, &Path)> {
668        self.paths.iter().find(|(_, p)| p.active())
669    }
670
671    /// Gets an immutable reference to the active path with the lowest
672    /// identifier. If there is no active path, returns an [`InvalidState`].
673    ///
674    /// [`InvalidState`]: enum.Error.html#variant.InvalidState
675    #[inline]
676    pub fn get_active(&self) -> Result<&Path> {
677        self.get_active_with_pid()
678            .map(|(_, p)| p)
679            .ok_or(Error::InvalidState)
680    }
681
682    /// Gets the lowest active path identifier. If there is no active path,
683    /// returns an [`InvalidState`].
684    ///
685    /// [`InvalidState`]: enum.Error.html#variant.InvalidState
686    #[inline]
687    pub fn get_active_path_id(&self) -> Result<usize> {
688        self.get_active_with_pid()
689            .map(|(pid, _)| pid)
690            .ok_or(Error::InvalidState)
691    }
692
693    /// Gets an mutable reference to the active path with the lowest identifier.
694    /// If there is no active path, returns an [`InvalidState`].
695    ///
696    /// [`InvalidState`]: enum.Error.html#variant.InvalidState
697    #[inline]
698    pub fn get_active_mut(&mut self) -> Result<&mut Path> {
699        self.paths
700            .iter_mut()
701            .map(|(_, p)| p)
702            .find(|p| p.active())
703            .ok_or(Error::InvalidState)
704    }
705
706    /// Returns an iterator over all existing paths.
707    #[inline]
708    pub fn iter(&self) -> slab::Iter<'_, Path> {
709        self.paths.iter()
710    }
711
712    /// Returns a mutable iterator over all existing paths.
713    #[inline]
714    pub fn iter_mut(&mut self) -> slab::IterMut<'_, Path> {
715        self.paths.iter_mut()
716    }
717
718    /// Returns the number of existing paths.
719    #[inline]
720    pub fn len(&self) -> usize {
721        self.paths.len()
722    }
723
724    /// Returns the `Path` identifier related to the provided `addrs`.
725    #[inline]
726    pub fn path_id_from_addrs(
727        &self, addrs: &(SocketAddr, SocketAddr),
728    ) -> Option<usize> {
729        self.addrs_to_paths.get(addrs).copied()
730    }
731
732    /// Checks if creating a new path will not exceed the current `self.paths`
733    /// capacity. If yes, this method tries to remove one unused path. If it
734    /// fails to do so, returns [`Done`].
735    ///
736    /// [`Done`]: enum.Error.html#variant.Done
737    fn make_room_for_new_path(&mut self) -> Result<()> {
738        if self.paths.len() < self.max_concurrent_paths {
739            return Ok(());
740        }
741
742        let (pid_to_remove, _) = self
743            .paths
744            .iter()
745            .find(|(_, p)| p.unused())
746            .ok_or(Error::Done)?;
747
748        let path = self.paths.remove(pid_to_remove);
749        self.addrs_to_paths
750            .remove(&(path.local_addr, path.peer_addr));
751
752        self.notify_event(PathEvent::Closed(path.local_addr, path.peer_addr));
753
754        Ok(())
755    }
756
757    /// Records the provided `Path` and returns its assigned identifier.
758    ///
759    /// On success, this method takes care of creating a notification to the
760    /// serving application, if it serves a server-side connection.
761    ///
762    /// If there are already `max_concurrent_paths` currently recorded, this
763    /// method tries to remove an unused `Path` first. If it fails to do so,
764    /// it returns [`Done`].
765    ///
766    /// [`Done`]: enum.Error.html#variant.Done
767    pub fn insert_path(&mut self, path: Path, is_server: bool) -> Result<usize> {
768        self.make_room_for_new_path()?;
769
770        let local_addr = path.local_addr;
771        let peer_addr = path.peer_addr;
772
773        let pid = self.paths.insert(path);
774        self.addrs_to_paths.insert((local_addr, peer_addr), pid);
775
776        // Notifies the application if we are in server mode.
777        if is_server {
778            self.notify_event(PathEvent::New(local_addr, peer_addr));
779        }
780
781        Ok(pid)
782    }
783
784    /// Notifies a path event to the application served by the connection.
785    pub fn notify_event(&mut self, ev: PathEvent) {
786        self.events.push_back(ev);
787    }
788
789    /// Gets the first path event to be notified to the application.
790    pub fn pop_event(&mut self) -> Option<PathEvent> {
791        self.events.pop_front()
792    }
793
794    /// Notifies all failed validations to the application.
795    pub fn notify_failed_validations(&mut self) {
796        let validation_failed = self
797            .paths
798            .iter_mut()
799            .filter(|(_, p)| p.validation_failed() && !p.failure_notified);
800
801        for (_, p) in validation_failed {
802            self.events.push_back(PathEvent::FailedValidation(
803                p.local_addr,
804                p.peer_addr,
805            ));
806
807            p.failure_notified = true;
808        }
809    }
810
811    /// Finds a path candidate to be active and returns its identifier.
812    pub fn find_candidate_path(&self) -> Option<usize> {
813        // TODO: also consider unvalidated paths if there are no more validated.
814        self.paths
815            .iter()
816            .find(|(_, p)| p.usable())
817            .map(|(pid, _)| pid)
818    }
819
820    /// Handles incoming PATH_RESPONSE data.
821    pub fn on_response_received(&mut self, data: [u8; 8]) -> Result<()> {
822        let active_pid = self.get_active_path_id()?;
823
824        let challenge_pending =
825            self.iter_mut().find(|(_, p)| p.has_pending_challenge(data));
826
827        if let Some((pid, p)) = challenge_pending {
828            if p.on_response_received(data) {
829                let local_addr = p.local_addr;
830                let peer_addr = p.peer_addr;
831                let was_migrating = p.migrating;
832
833                p.migrating = false;
834
835                // Notifies the application.
836                self.notify_event(PathEvent::Validated(local_addr, peer_addr));
837
838                // If this path was the candidate for migration, notifies the
839                // application.
840                if pid == active_pid && was_migrating {
841                    self.notify_event(PathEvent::PeerMigrated(
842                        local_addr, peer_addr,
843                    ));
844                }
845            }
846        }
847        Ok(())
848    }
849
850    /// Sets the path with identifier 'path_id' to be active.
851    ///
852    /// There can be exactly one active path on which non-probing packets can be
853    /// sent. If another path is marked as active, it will be superseded by the
854    /// one having `path_id` as identifier.
855    ///
856    /// A server should always ensure that the active path is validated. If it
857    /// is already the case, it notifies the application that the connection
858    /// migrated. Otherwise, it triggers a path validation and defers the
859    /// notification once it is actually validated.
860    pub fn set_active_path(&mut self, path_id: usize) -> Result<()> {
861        let is_server = self.is_server;
862
863        if let Ok(old_active_path) = self.get_active_mut() {
864            old_active_path.active = false;
865        }
866
867        let new_active_path = self.get_mut(path_id)?;
868        new_active_path.active = true;
869
870        if is_server {
871            if new_active_path.validated() {
872                let local_addr = new_active_path.local_addr();
873                let peer_addr = new_active_path.peer_addr();
874
875                self.notify_event(PathEvent::PeerMigrated(local_addr, peer_addr));
876            } else {
877                new_active_path.migrating = true;
878
879                // Requests path validation if needed.
880                if !new_active_path.under_validation() {
881                    new_active_path.request_validation();
882                }
883            }
884        }
885
886        Ok(())
887    }
888
889    /// Configures path MTU discovery on all existing paths.
890    pub fn set_discover_pmtu_on_existing_paths(
891        &mut self, discover: bool, max_send_udp_payload_size: usize,
892    ) {
893        for (_, path) in self.paths.iter_mut() {
894            path.pmtud = if discover {
895                Some(pmtud::Pmtud::new(max_send_udp_payload_size))
896            } else {
897                None
898            };
899        }
900    }
901}
902
903/// Statistics about the path of a connection.
904///
905/// A connection’s path statistics can be collected using the [`path_stats()`]
906/// method.
907///
908/// [`path_stats()`]: struct.Connection.html#method.path_stats
909#[derive(Clone)]
910pub struct PathStats {
911    /// The local address of the path.
912    pub local_addr: SocketAddr,
913
914    /// The peer address of the path.
915    pub peer_addr: SocketAddr,
916
917    /// The path validation state.
918    pub validation_state: PathState,
919
920    /// Whether the path is marked as active.
921    pub active: bool,
922
923    /// The number of QUIC packets received.
924    pub recv: usize,
925
926    /// The number of QUIC packets sent.
927    pub sent: usize,
928
929    /// The number of QUIC packets that were lost.
930    pub lost: usize,
931
932    /// The number of sent QUIC packets with retransmitted data.
933    pub retrans: usize,
934
935    /// The number of times PTO (probe timeout) fired.
936    ///
937    /// Loss usually happens in a burst so the number of packets lost will
938    /// depend on the volume of inflight packets at the time of loss (which
939    /// can be arbitrary). PTO count measures the number of loss events and
940    /// provides a normalized loss metric.
941    pub total_pto_count: usize,
942
943    /// The number of DATAGRAM frames received.
944    pub dgram_recv: usize,
945
946    /// The number of DATAGRAM frames sent.
947    pub dgram_sent: usize,
948
949    /// The estimated round-trip time of the connection.
950    pub rtt: Duration,
951
952    /// The minimum round-trip time observed.
953    pub min_rtt: Option<Duration>,
954
955    /// The maximum round-trip time observed.
956    pub max_rtt: Option<Duration>,
957
958    /// The estimated round-trip time variation in samples using a mean
959    /// variation.
960    pub rttvar: Duration,
961
962    /// The size of the connection's congestion window in bytes.
963    pub cwnd: usize,
964
965    /// The number of sent bytes.
966    pub sent_bytes: u64,
967
968    /// The number of received bytes.
969    pub recv_bytes: u64,
970
971    /// The number of bytes lost.
972    pub lost_bytes: u64,
973
974    /// The number of stream bytes retransmitted.
975    pub stream_retrans_bytes: u64,
976
977    /// The current PMTU for the connection.
978    pub pmtu: usize,
979
980    /// The most recent data delivery rate estimate in bytes/s.
981    ///
982    /// Note that this value could be inaccurate if the application does not
983    /// respect pacing hints (see [`SendInfo.at`] and [Pacing] for more
984    /// details).
985    ///
986    /// [`SendInfo.at`]: struct.SendInfo.html#structfield.at
987    /// [Pacing]: index.html#pacing
988    pub delivery_rate: u64,
989
990    /// The maximum bandwidth estimate for the connection in bytes/s.
991    ///
992    /// Note: not all congestion control algorithms provide this metric;
993    /// it is currently only implemented for bbr2_gcongestion.
994    pub max_bandwidth: Option<u64>,
995
996    /// Statistics from when a CCA first exited the startup phase.
997    pub startup_exit: Option<StartupExit>,
998}
999
1000impl std::fmt::Debug for PathStats {
1001    #[inline]
1002    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
1003        write!(
1004            f,
1005            "local_addr={:?} peer_addr={:?} ",
1006            self.local_addr, self.peer_addr,
1007        )?;
1008        write!(
1009            f,
1010            "validation_state={:?} active={} ",
1011            self.validation_state, self.active,
1012        )?;
1013        write!(
1014            f,
1015            "recv={} sent={} lost={} retrans={} rtt={:?} min_rtt={:?} rttvar={:?} cwnd={}",
1016            self.recv, self.sent, self.lost, self.retrans, self.rtt, self.min_rtt, self.rttvar, self.cwnd,
1017        )?;
1018
1019        write!(
1020            f,
1021            " sent_bytes={} recv_bytes={} lost_bytes={}",
1022            self.sent_bytes, self.recv_bytes, self.lost_bytes,
1023        )?;
1024
1025        write!(
1026            f,
1027            " stream_retrans_bytes={} pmtu={} delivery_rate={}",
1028            self.stream_retrans_bytes, self.pmtu, self.delivery_rate,
1029        )
1030    }
1031}
1032
1033#[cfg(test)]
1034mod tests {
1035    use crate::rand;
1036    use crate::MIN_CLIENT_INITIAL_LEN;
1037
1038    use crate::recovery::RecoveryConfig;
1039    use crate::Config;
1040
1041    use super::*;
1042
1043    #[test]
1044    fn path_validation_limited_mtu() {
1045        let client_addr = "127.0.0.1:1234".parse().unwrap();
1046        let client_addr_2 = "127.0.0.1:5678".parse().unwrap();
1047        let server_addr = "127.0.0.1:4321".parse().unwrap();
1048
1049        let config = Config::new(crate::PROTOCOL_VERSION).unwrap();
1050        let recovery_config = RecoveryConfig::from_config(&config);
1051
1052        let path = Path::new(
1053            client_addr,
1054            server_addr,
1055            &recovery_config,
1056            config.path_challenge_recv_max_queue_len,
1057            true,
1058            None,
1059        );
1060        let mut path_mgr = PathMap::new(path, 2, false);
1061
1062        let probed_path = Path::new(
1063            client_addr_2,
1064            server_addr,
1065            &recovery_config,
1066            config.path_challenge_recv_max_queue_len,
1067            false,
1068            None,
1069        );
1070        path_mgr.insert_path(probed_path, false).unwrap();
1071
1072        let pid = path_mgr
1073            .path_id_from_addrs(&(client_addr_2, server_addr))
1074            .unwrap();
1075        path_mgr.get_mut(pid).unwrap().request_validation();
1076        assert!(path_mgr.get_mut(pid).unwrap().validation_requested());
1077        assert!(path_mgr.get_mut(pid).unwrap().probing_required());
1078
1079        // Fake sending of PathChallenge in a packet of MIN_CLIENT_INITIAL_LEN - 1
1080        // bytes.
1081        let data = rand::rand_u64().to_be_bytes();
1082        path_mgr.get_mut(pid).unwrap().add_challenge_sent(
1083            data,
1084            MIN_CLIENT_INITIAL_LEN - 1,
1085            Instant::now(),
1086        );
1087
1088        assert!(!path_mgr.get_mut(pid).unwrap().validation_requested());
1089        assert!(!path_mgr.get_mut(pid).unwrap().probing_required());
1090        assert!(path_mgr.get_mut(pid).unwrap().under_validation());
1091        assert!(!path_mgr.get_mut(pid).unwrap().validated());
1092        assert_eq!(path_mgr.get_mut(pid).unwrap().state, PathState::Validating);
1093        assert_eq!(path_mgr.pop_event(), None);
1094
1095        // Receives the response. The path is reachable, but the MTU is not
1096        // validated yet.
1097        path_mgr.on_response_received(data).unwrap();
1098
1099        assert!(path_mgr.get_mut(pid).unwrap().validation_requested());
1100        assert!(path_mgr.get_mut(pid).unwrap().probing_required());
1101        assert!(path_mgr.get_mut(pid).unwrap().under_validation());
1102        assert!(!path_mgr.get_mut(pid).unwrap().validated());
1103        assert_eq!(
1104            path_mgr.get_mut(pid).unwrap().state,
1105            PathState::ValidatingMTU
1106        );
1107        assert_eq!(path_mgr.pop_event(), None);
1108
1109        // Fake sending of PathChallenge in a packet of MIN_CLIENT_INITIAL_LEN
1110        // bytes.
1111        let data = rand::rand_u64().to_be_bytes();
1112        path_mgr.get_mut(pid).unwrap().add_challenge_sent(
1113            data,
1114            MIN_CLIENT_INITIAL_LEN,
1115            Instant::now(),
1116        );
1117
1118        path_mgr.on_response_received(data).unwrap();
1119
1120        assert!(!path_mgr.get_mut(pid).unwrap().validation_requested());
1121        assert!(!path_mgr.get_mut(pid).unwrap().probing_required());
1122        assert!(!path_mgr.get_mut(pid).unwrap().under_validation());
1123        assert!(path_mgr.get_mut(pid).unwrap().validated());
1124        assert_eq!(path_mgr.get_mut(pid).unwrap().state, PathState::Validated);
1125        assert_eq!(
1126            path_mgr.pop_event(),
1127            Some(PathEvent::Validated(client_addr_2, server_addr))
1128        );
1129    }
1130
1131    #[test]
1132    fn multiple_probes() {
1133        let client_addr = "127.0.0.1:1234".parse().unwrap();
1134        let server_addr = "127.0.0.1:4321".parse().unwrap();
1135
1136        let config = Config::new(crate::PROTOCOL_VERSION).unwrap();
1137        let recovery_config = RecoveryConfig::from_config(&config);
1138
1139        let path = Path::new(
1140            client_addr,
1141            server_addr,
1142            &recovery_config,
1143            config.path_challenge_recv_max_queue_len,
1144            true,
1145            None,
1146        );
1147        let mut client_path_mgr = PathMap::new(path, 2, false);
1148        let mut server_path = Path::new(
1149            server_addr,
1150            client_addr,
1151            &recovery_config,
1152            config.path_challenge_recv_max_queue_len,
1153            false,
1154            None,
1155        );
1156
1157        let client_pid = client_path_mgr
1158            .path_id_from_addrs(&(client_addr, server_addr))
1159            .unwrap();
1160
1161        // First probe.
1162        let data = rand::rand_u64().to_be_bytes();
1163
1164        client_path_mgr
1165            .get_mut(client_pid)
1166            .unwrap()
1167            .add_challenge_sent(data, MIN_CLIENT_INITIAL_LEN, Instant::now());
1168
1169        // Second probe.
1170        let data_2 = rand::rand_u64().to_be_bytes();
1171
1172        client_path_mgr
1173            .get_mut(client_pid)
1174            .unwrap()
1175            .add_challenge_sent(data_2, MIN_CLIENT_INITIAL_LEN, Instant::now());
1176        assert_eq!(
1177            client_path_mgr
1178                .get(client_pid)
1179                .unwrap()
1180                .in_flight_challenges
1181                .len(),
1182            2
1183        );
1184
1185        // If we receive multiple challenges, we can store them.
1186        server_path.on_challenge_received(data);
1187        assert_eq!(server_path.received_challenges.len(), 1);
1188        server_path.on_challenge_received(data_2);
1189        assert_eq!(server_path.received_challenges.len(), 2);
1190
1191        // Response for first probe.
1192        client_path_mgr.on_response_received(data).unwrap();
1193        assert_eq!(
1194            client_path_mgr
1195                .get(client_pid)
1196                .unwrap()
1197                .in_flight_challenges
1198                .len(),
1199            1
1200        );
1201
1202        // Response for second probe.
1203        client_path_mgr.on_response_received(data_2).unwrap();
1204        assert_eq!(
1205            client_path_mgr
1206                .get(client_pid)
1207                .unwrap()
1208                .in_flight_challenges
1209                .len(),
1210            0
1211        );
1212    }
1213
1214    #[test]
1215    fn too_many_probes() {
1216        let client_addr = "127.0.0.1:1234".parse().unwrap();
1217        let server_addr = "127.0.0.1:4321".parse().unwrap();
1218
1219        // Default to DEFAULT_MAX_PATH_CHALLENGE_RX_QUEUE_LEN
1220        let config = Config::new(crate::PROTOCOL_VERSION).unwrap();
1221        let recovery_config = RecoveryConfig::from_config(&config);
1222
1223        let path = Path::new(
1224            client_addr,
1225            server_addr,
1226            &recovery_config,
1227            config.path_challenge_recv_max_queue_len,
1228            true,
1229            None,
1230        );
1231        let mut client_path_mgr = PathMap::new(path, 2, false);
1232        let mut server_path = Path::new(
1233            server_addr,
1234            client_addr,
1235            &recovery_config,
1236            config.path_challenge_recv_max_queue_len,
1237            false,
1238            None,
1239        );
1240
1241        let client_pid = client_path_mgr
1242            .path_id_from_addrs(&(client_addr, server_addr))
1243            .unwrap();
1244
1245        // First probe.
1246        let data = rand::rand_u64().to_be_bytes();
1247
1248        client_path_mgr
1249            .get_mut(client_pid)
1250            .unwrap()
1251            .add_challenge_sent(data, MIN_CLIENT_INITIAL_LEN, Instant::now());
1252
1253        // Second probe.
1254        let data_2 = rand::rand_u64().to_be_bytes();
1255
1256        client_path_mgr
1257            .get_mut(client_pid)
1258            .unwrap()
1259            .add_challenge_sent(data_2, MIN_CLIENT_INITIAL_LEN, Instant::now());
1260        assert_eq!(
1261            client_path_mgr
1262                .get(client_pid)
1263                .unwrap()
1264                .in_flight_challenges
1265                .len(),
1266            2
1267        );
1268
1269        // Third probe.
1270        let data_3 = rand::rand_u64().to_be_bytes();
1271
1272        client_path_mgr
1273            .get_mut(client_pid)
1274            .unwrap()
1275            .add_challenge_sent(data_3, MIN_CLIENT_INITIAL_LEN, Instant::now());
1276        assert_eq!(
1277            client_path_mgr
1278                .get(client_pid)
1279                .unwrap()
1280                .in_flight_challenges
1281                .len(),
1282            3
1283        );
1284
1285        // Fourth probe.
1286        let data_4 = rand::rand_u64().to_be_bytes();
1287
1288        client_path_mgr
1289            .get_mut(client_pid)
1290            .unwrap()
1291            .add_challenge_sent(data_4, MIN_CLIENT_INITIAL_LEN, Instant::now());
1292        assert_eq!(
1293            client_path_mgr
1294                .get(client_pid)
1295                .unwrap()
1296                .in_flight_challenges
1297                .len(),
1298            4
1299        );
1300
1301        // If we receive multiple challenges, we can store them up to our queue
1302        // size.
1303        server_path.on_challenge_received(data);
1304        assert_eq!(server_path.received_challenges.len(), 1);
1305        server_path.on_challenge_received(data_2);
1306        assert_eq!(server_path.received_challenges.len(), 2);
1307        server_path.on_challenge_received(data_3);
1308        assert_eq!(server_path.received_challenges.len(), 3);
1309        server_path.on_challenge_received(data_4);
1310        assert_eq!(server_path.received_challenges.len(), 3);
1311
1312        // Response for first probe.
1313        client_path_mgr.on_response_received(data).unwrap();
1314        assert_eq!(
1315            client_path_mgr
1316                .get(client_pid)
1317                .unwrap()
1318                .in_flight_challenges
1319                .len(),
1320            3
1321        );
1322
1323        // Response for second probe.
1324        client_path_mgr.on_response_received(data_2).unwrap();
1325        assert_eq!(
1326            client_path_mgr
1327                .get(client_pid)
1328                .unwrap()
1329                .in_flight_challenges
1330                .len(),
1331            2
1332        );
1333
1334        // Response for third probe.
1335        client_path_mgr.on_response_received(data_3).unwrap();
1336        assert_eq!(
1337            client_path_mgr
1338                .get(client_pid)
1339                .unwrap()
1340                .in_flight_challenges
1341                .len(),
1342            1
1343        );
1344
1345        // There will never be a response for fourth probe...
1346    }
1347}