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}