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