Skip to main content

zond_engine/model/host/
path.rs

1// Copyright (c) 2026 Erik Lening (hollowpointer) and Contributors
2//
3// This file is part of Zond Engine, licensed under the GNU Affero General
4// Public License, version 3 or later. See the LICENSE file for details, or
5// <https://www.gnu.org/licenses/agpl-3.0.html>.
6//
7// SPDX-License-Identifier: AGPL-3.0-or-later
8
9//! # The route a probe took to reach a host
10//!
11//! [`NetworkPath`] is the sequence of routers between this machine and one target, as
12//! a traceroute establishes it: a finding about the space *between* two addresses.
13//!
14//! ## A hop is a distance
15//!
16//! Every [`Hop`] carries the [`distance`](Hop::distance) it was measured at (the hop
17//! limit whose expiry produced it), independent of its position in the list:
18//!
19//! - **A router may decline to answer.** Many never send Time Exceeded, or rate-limit
20//!   it to nothing. The gap stays, so routers beyond it keep their numbers.
21//! - **A path may be spliced.** When one trace meets a router another trace found, the
22//!   rest is taken from the earlier trace; see [`Hop::inferred`]. Those hops keep their
23//!   original distances.
24//!
25//! So a path is sorted by distance and may have holes; ask for distance three, not
26//! index two.
27//!
28//! ## A router the scan may not name
29//!
30//! A router whose address falls under the scan's
31//! [`Exclusions`](crate::model::exclusion::Exclusions) keeps its distance and loses its
32//! address; see [`Hop::withheld`]. A trace hears from such a router without sending to
33//! it, so recording is the only part of the policy a path could break. Recording it as
34//! silent would claim nothing answered, and leaving it out could make the path read a
35//! router shorter.
36//!
37//! ## What a hop establishes
38//!
39//! A router at that address discarded a packet of ours that had travelled that far. A
40//! router must identify itself when it discards a packet (RFC 792, RFC 4443 §3.3).
41//!
42//! The address is the one the router chose to reply from, not always the interface
43//! the probe used, so two traces can name different addresses for one device.
44//!
45//! A round-trip time is measured from this machine to the router, so hop three's
46//! includes hops one and two. Routers treat generating errors as low priority, so a hop
47//! slower than the next is ordinary.
48
49use std::net::IpAddr;
50use std::time::Duration;
51
52/// One router on the way to a host, at a known distance.
53#[derive(Debug, Clone, Copy, PartialEq, Eq)]
54pub struct Hop {
55    distance: u8,
56    answer: Answer,
57    rtt: Option<Duration>,
58    inferred: bool,
59}
60
61/// What was heard from a distance.
62///
63/// One value, so a withheld hop carrying an address cannot be built.
64#[derive(Debug, Clone, Copy, PartialEq, Eq)]
65enum Answer {
66    /// Nothing answered.
67    Silent,
68    /// A router answered, from this address.
69    Router(IpAddr),
70    /// A router answered, from an address the scan may not report.
71    Withheld,
72}
73
74impl Hop {
75    /// A router that answered, at `distance` hops, in `rtt`.
76    pub fn answered(distance: u8, address: IpAddr, rtt: Option<Duration>) -> Self {
77        Self {
78            distance,
79            answer: Answer::Router(address),
80            rtt,
81            inferred: false,
82        }
83    }
84
85    /// A distance nothing answered at.
86    ///
87    /// Recorded, since omitting it would make the path read shorter than it is.
88    pub fn silent(distance: u8) -> Self {
89        Self {
90            distance,
91            answer: Answer::Silent,
92            rtt: None,
93            inferred: false,
94        }
95    }
96
97    /// A distance a router answered at, from an address the scan's exclusions
98    /// forbid it to report.
99    ///
100    /// See the module documentation. Carries no round trip, which would be a fact about
101    /// the router.
102    ///
103    /// For reading a record back; a scan records a router as it answered and withholds
104    /// the address afterwards.
105    pub fn withheld(distance: u8) -> Self {
106        Self {
107            distance,
108            answer: Answer::Withheld,
109            rtt: None,
110            inferred: false,
111        }
112    }
113
114    /// The same hop, marked as taken from another host's trace rather than
115    /// measured on this one. See [`inferred`](Self::inferred).
116    #[must_use]
117    pub fn as_inferred(mut self) -> Self {
118        self.inferred = true;
119        // A round trip belongs to the trace that measured it.
120        self.rtt = None;
121        self
122    }
123
124    /// How many hops from this machine this router sits.
125    pub fn distance(&self) -> u8 {
126        self.distance
127    }
128
129    /// The address the router answered from, or `None` if nothing answered at
130    /// this distance or the address is [withheld](Self::is_withheld).
131    pub fn address(&self) -> Option<IpAddr> {
132        match self.answer {
133            Answer::Router(address) => Some(address),
134            Answer::Silent | Answer::Withheld => None,
135        }
136    }
137
138    /// How long the probe that expired here took to be answered, measured from
139    /// this machine. `None` for a silent hop, an inferred one and a withheld
140    /// one.
141    pub fn rtt(&self) -> Option<Duration> {
142        self.rtt
143    }
144
145    /// Whether a router answered here from an address the scan may not report.
146    ///
147    /// The one case where [`address`](Self::address) is `None` but something answered,
148    /// so check it before drawing a gap. See [`withheld`](Self::withheld).
149    pub fn is_withheld(&self) -> bool {
150        self.answer == Answer::Withheld
151    }
152
153    /// Whether anything answered at this distance, whether or not the report
154    /// may say what.
155    fn is_answer(&self) -> bool {
156        self.answer != Answer::Silent
157    }
158
159    /// Whether this hop was measured on the way to *this* host, or copied from
160    /// an earlier trace that passed through the same router.
161    ///
162    /// A spliced path assumes the two hosts share everything upstream of the router
163    /// where the traces met, which is nearly always true but still an assumption.
164    pub fn inferred(&self) -> bool {
165        self.inferred
166    }
167}
168
169/// The routers between this machine and one host, in order of distance.
170///
171/// Sorted by distance, with at most one hop per distance. [`record`](Self::record) is
172/// the only way in; withholding an address rewrites a hop in place.
173#[derive(Debug, Clone, Default, PartialEq, Eq)]
174pub struct NetworkPath {
175    hops: Vec<Hop>,
176}
177
178impl NetworkPath {
179    /// An empty path.
180    pub fn new() -> Self {
181        Self::default()
182    }
183
184    /// Records `hop`, replacing whatever was known at that distance.
185    ///
186    /// An answered hop replaces a silent one, since silence is the absence of a
187    /// finding. Between two that agree on that, a measurement replaces an inference
188    /// and never the reverse. A [withheld](Hop::withheld) hop counts as answered.
189    pub fn record(&mut self, hop: Hop) {
190        match self
191            .hops
192            .binary_search_by_key(&hop.distance, |known| known.distance)
193        {
194            Ok(index) => {
195                let known = &self.hops[index];
196                // Ranked: whether anything answered first, then provenance.
197                // Otherwise a measured silence could displace an inferred answer,
198                // which `Host::merge` replaying hops in either order would reach.
199                let stronger = match (known.is_answer(), hop.is_answer()) {
200                    (false, true) => true,
201                    (true, false) => false,
202                    _ => known.inferred && !hop.inferred,
203                };
204                if stronger {
205                    self.hops[index] = hop;
206                }
207            }
208            Err(index) => self.hops.insert(index, hop),
209        }
210    }
211
212    /// Withholds the address of every router `keep` refuses, and returns
213    /// whether it withheld any.
214    ///
215    /// For the exclusion policy. Each refused hop becomes [`Hop::withheld`] at the same
216    /// distance and provenance, losing its round trip with its address.
217    pub(crate) fn withhold(&mut self, keep: impl Fn(&IpAddr) -> bool) -> bool {
218        let mut withheld = false;
219        for hop in &mut self.hops {
220            if let Answer::Router(address) = hop.answer
221                && !keep(&address)
222            {
223                *hop = Hop {
224                    inferred: hop.inferred,
225                    ..Hop::withheld(hop.distance)
226                };
227                withheld = true;
228            }
229        }
230        withheld
231    }
232
233    /// Every hop, ascending by distance. May have gaps; see the module docs.
234    pub fn hops(&self) -> &[Hop] {
235        &self.hops
236    }
237
238    /// Whether anything is known about the path at all.
239    pub fn is_empty(&self) -> bool {
240        self.hops.is_empty()
241    }
242
243    /// How far away the furthest known router is, or `None` for an empty path.
244    ///
245    /// The last *known* distance, which differs from a hop count when a router
246    /// declined to answer.
247    pub fn length(&self) -> Option<u8> {
248        self.hops.last().map(Hop::distance)
249    }
250
251    /// The address at `distance`, if a router answered there and its address
252    /// is not withheld.
253    pub fn at(&self, distance: u8) -> Option<IpAddr> {
254        self.hops
255            .binary_search_by_key(&distance, |hop| hop.distance)
256            .ok()
257            .and_then(|index| self.hops[index].address())
258    }
259}
260
261// ╔════════════════════════════════════════════╗
262// ║ ████████╗███████╗███████╗████████╗███████╗ ║
263// ║ ╚══██╔══╝██╔════╝██╔════╝╚══██╔══╝██╔════╝ ║
264// ║    ██║   █████╗  ███████╗   ██║   ███████╗ ║
265// ║    ██║   ██╔══╝  ╚════██║   ██║   ╚════██║ ║
266// ║    ██║   ███████╗███████║   ██║   ███████║ ║
267// ║    ╚═╝   ╚══════╝╚══════╝   ╚═╝   ╚══════╝ ║
268// ╚════════════════════════════════════════════╝
269
270#[cfg(test)]
271mod tests {
272    use super::*;
273    use std::net::Ipv4Addr;
274
275    fn ip(last: u8) -> IpAddr {
276        IpAddr::V4(Ipv4Addr::new(10, 0, 0, last))
277    }
278
279    /// An answer displaces silence whatever measured it, and provenance decides
280    /// only between two hops that agree about whether anything answered.
281    ///
282    /// A measured silent hop does not displace an inferred answered one.
283    #[test]
284    fn an_answer_is_never_traded_for_a_silence_that_measured_it() {
285        let spliced = Hop::answered(4, ip(4), None).as_inferred();
286
287        let mut path = NetworkPath::new();
288        path.record(spliced);
289        path.record(Hop::silent(4));
290        assert_eq!(
291            path.at(4),
292            Some(ip(4)),
293            "a measured silence does not erase a router somebody found"
294        );
295
296        // The other way round.
297        let mut reverse = NetworkPath::new();
298        reverse.record(Hop::silent(4));
299        reverse.record(spliced);
300        assert_eq!(reverse.at(4), Some(ip(4)));
301
302        // Where both answered, the measurement wins.
303        let mut both = NetworkPath::new();
304        both.record(Hop::answered(1, ip(9), None).as_inferred());
305        both.record(Hop::answered(1, ip(1), None));
306        assert_eq!(both.at(1), Some(ip(1)), "a measurement beats an inference");
307
308        // Where neither did, the measurement stands.
309        let mut neither = NetworkPath::new();
310        neither.record(Hop::silent(2));
311        neither.record(Hop::silent(2).as_inferred());
312        assert_eq!(neither.hops().len(), 1);
313        assert!(!neither.hops()[0].inferred());
314    }
315
316    /// Hops arrive in whatever order their replies do, and a path reads in
317    /// order of distance regardless.
318    ///
319    /// Traces probe concurrently, so hop five often answers before hop two.
320    #[test]
321    fn a_path_reads_in_order_of_distance_however_the_replies_arrived() {
322        let mut path = NetworkPath::new();
323        path.record(Hop::answered(3, ip(3), None));
324        path.record(Hop::answered(1, ip(1), None));
325        path.record(Hop::answered(2, ip(2), None));
326
327        let distances: Vec<u8> = path.hops().iter().map(Hop::distance).collect();
328        assert_eq!(distances, vec![1, 2, 3]);
329        assert_eq!(path.length(), Some(3));
330        assert_eq!(path.at(2), Some(ip(2)));
331    }
332
333    /// A router that will not answer leaves a hole, and the hole is the finding.
334    ///
335    /// Dropping it would make this three-router path read as two.
336    #[test]
337    fn a_silent_router_holds_its_place() {
338        let mut path = NetworkPath::new();
339        path.record(Hop::answered(1, ip(1), None));
340        path.record(Hop::silent(2));
341        path.record(Hop::answered(3, ip(3), None));
342
343        assert_eq!(path.hops().len(), 3);
344        assert_eq!(path.at(2), None);
345        assert_eq!(path.length(), Some(3), "the target is still three away");
346    }
347
348    /// What is known about a distance only ever gets stronger.
349    ///
350    /// The three transitions that must hold, and the three that must not, in either
351    /// arrival order.
352    #[test]
353    fn a_measurement_outranks_an_inference_and_an_answer_outranks_silence() {
354        let measured = Hop::answered(2, ip(2), Some(Duration::from_millis(5)));
355        let inferred = Hop::answered(2, ip(9), None).as_inferred();
356
357        let mut upgrading = NetworkPath::new();
358        upgrading.record(inferred);
359        upgrading.record(measured);
360        assert_eq!(upgrading.at(2), Some(ip(2)));
361        assert!(!upgrading.hops()[0].inferred());
362
363        let mut downgrading = NetworkPath::new();
364        downgrading.record(measured);
365        downgrading.record(inferred);
366        assert_eq!(downgrading.at(2), Some(ip(2)), "a measurement is not lost");
367        assert_eq!(downgrading.hops()[0].rtt(), Some(Duration::from_millis(5)));
368
369        let mut filling = NetworkPath::new();
370        filling.record(Hop::silent(2));
371        filling.record(measured);
372        assert_eq!(filling.at(2), Some(ip(2)));
373
374        let mut keeping = NetworkPath::new();
375        keeping.record(measured);
376        keeping.record(Hop::silent(2));
377        assert_eq!(
378            keeping.at(2),
379            Some(ip(2)),
380            "silence does not erase an answer"
381        );
382    }
383
384    /// A withheld router ranks as the answer it was, not as the silence its
385    /// missing address resembles.
386    ///
387    /// A measured silence does not displace a spliced router whose address was
388    /// withheld.
389    #[test]
390    fn a_withheld_router_still_outranks_silence() {
391        let spliced = Hop::withheld(3).as_inferred();
392
393        let mut path = NetworkPath::new();
394        path.record(spliced);
395        path.record(Hop::silent(3));
396        assert!(path.hops()[0].is_withheld(), "{path:?}");
397
398        // Between two answers, provenance still decides.
399        let mut measured = NetworkPath::new();
400        measured.record(Hop::answered(3, ip(3), None).as_inferred());
401        measured.record(Hop::withheld(3));
402        assert!(measured.hops()[0].is_withheld());
403        assert!(!measured.hops()[0].inferred());
404    }
405
406    /// Withholding keeps the distance and provenance and drops the address and round
407    /// trip.
408    #[test]
409    fn withholding_a_router_keeps_its_place_and_its_provenance() {
410        let mut path = NetworkPath::new();
411        path.record(Hop::answered(1, ip(1), Some(Duration::from_millis(1))));
412        path.record(Hop::answered(2, ip(2), Some(Duration::from_millis(2))).as_inferred());
413        path.record(Hop::answered(3, ip(3), Some(Duration::from_millis(3))));
414
415        assert!(path.withhold(|address| *address != ip(2)));
416
417        let withheld = path.hops()[1];
418        assert_eq!(withheld.distance(), 2);
419        assert!(withheld.is_withheld());
420        assert!(withheld.inferred(), "a spliced router stays marked as one");
421        assert_eq!(withheld.address(), None);
422        assert_eq!(withheld.rtt(), None);
423        assert_eq!(path.at(1), Some(ip(1)), "a permitted router is untouched");
424        assert_eq!(path.length(), Some(3));
425
426        assert!(
427            !path.withhold(|address| *address != ip(2)),
428            "there is nothing left to withhold"
429        );
430    }
431
432    /// An inferred hop carries no round-trip time.
433    #[test]
434    fn an_inferred_hop_reports_no_timing_of_its_own() {
435        let inferred = Hop::answered(4, ip(4), Some(Duration::from_millis(9))).as_inferred();
436
437        assert!(inferred.inferred());
438        assert_eq!(inferred.address(), Some(ip(4)));
439        assert_eq!(inferred.rtt(), None);
440    }
441}