Skip to main content

zond_engine/system/interface/
routing.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//! # How this host reaches a target
10//!
11//! A target is on a segment this machine is attached to, behind a gateway, or
12//! reachable by neither, and that decides whether it gets a link-layer sweep, a
13//! raw probe with a source address, or the unprivileged fallback.
14//!
15//! A segment is a link a frame can be put on. A tunnel's address carries a prefix
16//! too, and a WireGuard peer or an OpenVPN server in subnet topology sits inside
17//! it, but nothing beyond a tunnel answers ARP or neighbour discovery, so a target
18//! inside that prefix is probed through the tunnel like any routed target.
19//!
20//! ## Refusals
21//!
22//! Two of the five buckets [`RoutedTargets`] hands back are refusals. A bare IPv6
23//! link-local matches every interface and identifies none, so it is reported as
24//! ambiguous. An off-link IPv6 range past [`MAX_ENUMERABLE_ADDRESSES`] is kept
25//! whole and refused, because the only strategy for an off-link range is to walk
26//! it. Both are carried out so a scan never stays quiet about ground it did not
27//! look at.
28//!
29//! ## What a frame reaches
30//!
31//! A process that can inject frames but holds no raw socket (an unprivileged run
32//! on macOS holding the BPF devices, a privileged one on Windows) reaches only
33//! targets with Ethernet in front of them. [`beyond_frames`] names the rest and
34//! why, so a scan can reach them by connect.
35//!
36//! ## Cost
37//!
38//! One `connect` per off-link target on an unbound UDP socket, which performs a
39//! route lookup and sends nothing, parallelised across the target list. On-link
40//! targets cost a prefix comparison and no syscall.
41
42use crate::model::ip::range::IpRange::{self, V4, V6};
43use crate::model::ip::range::{Ipv4Range, Ipv6Range};
44use crate::model::ip::scoped::ScopedIp;
45use crate::model::ip::set::IpSet;
46use crate::system::interface::source::{
47    RouteAnswer, ask_route, plausible_source, refuses_neighbour, viable_interfaces,
48};
49use crate::system::interface::{Link, LinkAddress};
50use rayon::prelude::*;
51use std::collections::{HashMap, HashSet};
52use std::net::IpAddr;
53
54/// An off-link target paired with the local source address a probe to it must
55/// be sent from.
56#[non_exhaustive]
57#[derive(Debug, Clone, Copy, PartialEq, Eq)]
58pub struct RoutedTarget {
59    /// The destination being probed.
60    pub target: IpAddr,
61    /// The source address to send its probe from.
62    pub source: IpAddr,
63}
64
65impl RoutedTarget {
66    /// A probe of `target`, sent from `source`.
67    pub const fn new(target: IpAddr, source: IpAddr) -> Self {
68        Self { target, source }
69    }
70}
71
72/// The largest IPv6 range any strategy will turn into addresses one at a time.
73///
74/// 65,536 addresses, the size of an IPv4 `/16` and an IPv6 `/112`. Walking is
75/// the only discovery strategy for an off-link range, and a `/64` holds 2^64
76/// addresses: about 146 million years at a routed sweep's four thousand probes
77/// a second, and expanding it into a `Vec<IpAddr>` exhausts memory first.
78/// Larger IPv6 ranges are refused, loudly, so the caller knows the engine did
79/// not look.
80///
81/// IPv4 ranges are not bounded by this: the whole space is 2^32, and a `/8` is
82/// unreasonable but possible.
83///
84/// Ask through [`is_enumerable`]. The classifier applies it to a routed range
85/// it would have to walk; [`crate::scanner`] applies it on the unprivileged
86/// path, which has no classifier; and `DiscoveryPlan::build` applies it to an
87/// on-link range, which the classifier hands over whole because a segment is
88/// swept by multicast.
89pub const MAX_ENUMERABLE_ADDRESSES: u128 = 1 << 16;
90
91/// The result of classifying a set of targets against this host's interfaces
92/// and routing table.
93#[non_exhaustive]
94#[derive(Debug, Default)]
95pub struct RoutedTargets {
96    /// Targets that share an interface's Layer-2 segment, grouped by that
97    /// interface. Reachable directly, so they get an ARP/NDP discovery
98    /// strategy bound to the interface.
99    ///
100    /// Only a link that carries frames has a segment, except for a link-local
101    /// target whose zone names a link that does not: the zone is the user's own
102    /// statement of where the target is.
103    pub local: HashMap<Link, IpSet>,
104    /// Targets reached through a gateway or a tunnel, each already paired with
105    /// the source address to probe it from. Handled by a single raw TCP SYN
106    /// scanner.
107    pub routed: Vec<RoutedTarget>,
108    /// Targets that are neither on-link nor have a resolvable route, left to
109    /// the unprivileged connect fallback. Loopback is always here, in both
110    /// families, whatever the routing table or a forced source says about it.
111    pub unmapped: IpSet,
112    /// Targets that are this host's own addresses.
113    ///
114    /// No strategy can establish one: the kernel reaches an address the host
115    /// holds through loopback, so an ARP request for it goes unanswered. It is up
116    /// by construction.
117    pub ours: IpSet,
118    /// Link-local IPv6 targets with no interface named on them.
119    ///
120    /// Every interface holds an `fe80::/64`, so such a target matches all of
121    /// them and identifies none. Probing whichever the host listed first could
122    /// report the address absent when it is present on another segment. Written
123    /// `fe80::1%en0`, it is unambiguous.
124    pub ambiguous: Vec<Ipv6Range>,
125    /// Off-link IPv6 ranges too large to enumerate, kept whole.
126    ///
127    /// They were never probed. They are carried out so a caller reading "no hosts
128    /// found" does not take it as evidence about the range.
129    pub unenumerable: Vec<Ipv6Range>,
130}
131
132/// Classifies target IPs by how this host reaches them: on-link (per
133/// interface), routed through a gateway or a tunnel (paired with a source
134/// address), or unreachable.
135///
136/// Reads the host's interface table through
137/// [`interfaces`](super::interfaces), narrowed to the links that could carry a
138/// probe.
139pub fn map_ips_to_interfaces(ip_set: IpSet) -> RoutedTargets {
140    map_ips_to_interfaces_with(ip_set, viable_interfaces(), &[])
141}
142
143/// [`map_ips_to_interfaces`], with source addresses forced ahead of the routing
144/// table. A scan pinned to an interface routes every off-link target from that
145/// interface's address, for a host whose default route a VPN owns.
146pub(crate) fn map_ips_to_interfaces_forced(ip_set: IpSet, forced: &[IpAddr]) -> RoutedTargets {
147    map_ips_to_interfaces_with(ip_set, viable_interfaces(), forced)
148}
149
150/// Classification of one target, from the parallel pass, before the results
151/// are folded into interface-indexed buckets.
152enum Classification {
153    /// On-link on the interface at this index.
154    Local(usize),
155    /// Routed off-link, to be sent from this source address.
156    Routed(IpAddr),
157    /// An address this host holds.
158    Ours,
159    /// No route found.
160    Unmapped,
161}
162
163/// [`map_ips_to_interfaces`] against an interface table the caller supplies.
164///
165/// The seam the classification is tested through, with interfaces that do not
166/// exist.
167pub(crate) fn map_ips_to_interfaces_with(
168    ip_set: IpSet,
169    interfaces: Vec<Link>,
170    forced: &[IpAddr],
171) -> RoutedTargets {
172    map_ips_to_interfaces_asking(ip_set, interfaces, forced, ask_route)
173}
174
175/// [`map_ips_to_interfaces_with`], asking the routing table about a routed
176/// target through `route`, for a test that needs the table to answer as no test
177/// host does.
178fn map_ips_to_interfaces_asking(
179    ip_set: IpSet,
180    interfaces: Vec<Link>,
181    forced: &[IpAddr],
182    route: fn(IpAddr) -> RouteAnswer,
183) -> RoutedTargets {
184    let owned_ips: HashSet<IpAddr> = interfaces
185        .iter()
186        .flat_map(|link| link.addresses().iter().map(|held| held.address()))
187        .collect();
188
189    let mut local: HashMap<usize, IpSet> = HashMap::new();
190    let mut routed: Vec<RoutedTarget> = Vec::new();
191    let mut unmapped = IpSet::new();
192    let mut ours = IpSet::new();
193    let mut unenumerable: Vec<Ipv6Range> = Vec::new();
194    let mut ambiguous: Vec<Ipv6Range> = Vec::new();
195    let mut singles_to_route: Vec<IpAddr> = Vec::new();
196
197    // A range wholly inside one segment's subnet is kept intact; anything
198    // else is expanded to singles for per-target route resolution.
199    for range in ip_set.v4() {
200        let start = IpAddr::V4(range.start_addr());
201        let end = IpAddr::V4(range.end_addr());
202        match owning_interface(&interfaces, start, end) {
203            Some(idx) => local.entry(idx).or_default().insert_range(V4(*range)),
204            None => singles_to_route.extend(range.iter()),
205        }
206    }
207    for range in ip_set.v6() {
208        let start = IpAddr::V6(range.start_addr());
209        let end = IpAddr::V6(range.end_addr());
210
211        // Before any interface is consulted: they all match.
212        if range.is_ambiguous() {
213            ambiguous.push(*range);
214            continue;
215        }
216        // A named interface answers outright, ahead of any prefix match.
217        if let Some(zone) = range.zone() {
218            match interfaces.iter().position(|link| link.index() == zone) {
219                Some(idx) => local.entry(idx).or_default().insert_range(V6(*range)),
220                None => ambiguous.push(*range),
221            }
222            continue;
223        }
224
225        match owning_interface(&interfaces, start, end) {
226            // On-link, so kept whole: a segment is reached by multicast, one packet
227            // whatever the prefix length. Whether it is also small enough to walk is
228            // for `DiscoveryPlan::build` to ask.
229            Some(idx) => local.entry(idx).or_default().insert_range(V6(*range)),
230            // Off-link, so each address is probed in turn. Checked before `to_iter`
231            // because the expansion is what does the damage.
232            None if !is_enumerable(range) => unenumerable.push(*range),
233            None => singles_to_route.extend(range.iter()),
234        }
235    }
236
237    let processed: Vec<(IpAddr, Classification)> = singles_to_route
238        .par_iter()
239        .map(|&target| {
240            // Loopback is this host. The kernel answers `::1` with `::1`, which no
241            // interface here holds, and the fallback below would then pair it with a
242            // global source as if it were routed behind a VPN; a forced source would do
243            // the same. This keeps both loopbacks planned alike.
244            if target.is_loopback() {
245                return (target, Classification::Unmapped);
246            }
247            // An IPv4-mapped address is an IPv4 host written inside IPv6, and no wire
248            // carries one. Unmapped, it is left to the kernel, whose dual-stack socket
249            // reaches the IPv4 host.
250            if is_ipv4_mapped(target) {
251                return (target, Classification::Unmapped);
252            }
253            // Before any prefix: this host's address is inside its own link's prefix,
254            // and the kernel answers it from loopback.
255            if owned_ips.contains(&target) {
256                return (target, Classification::Ours);
257            }
258
259            // Inside a prefix this host holds, that link is the one route to the
260            // target: a segment is swept, and inside a tunnel's own prefix the target
261            // is reached through the tunnel from its address. A forced source must not
262            // move the target off that link.
263            if let Some((idx, held)) = holding_prefix(&interfaces, target) {
264                return if interfaces[idx].carries_frames() {
265                    (target, Classification::Local(idx))
266                } else {
267                    (target, Classification::Routed(held.address()))
268                };
269            }
270
271            // A route that refuses by policy is the host's decision, and neither a
272            // forced source nor the fallback below steps around it (the kernel sends
273            // from a named address wherever the table refuses). Left to the connect
274            // fallback, whose connect the kernel refuses too. See
275            // `RouteAnswer::Forbidden`.
276            let answer = route(target);
277            if matches!(answer, RouteAnswer::Forbidden) {
278                return (target, Classification::Unmapped);
279            }
280
281            // Otherwise a forced source outranks the routing table, for a routed
282            // target the kernel would send from the wrong interface.
283            if let Some(source) = forced
284                .iter()
285                .copied()
286                .find(|s| s.is_ipv4() == target.is_ipv4())
287            {
288                return (target, Classification::Routed(source));
289            }
290
291            if let RouteAnswer::From(source) = answer
292                && owned_ips.contains(&source)
293            {
294                return (target, Classification::Routed(source));
295            }
296
297            // No route, but this host may still hold an address of the right scope;
298            // see `plausible_source`. This covers a laptop whose VPN swallowed the IPv6
299            // default route.
300            if let Some(source) = plausible_source(&interfaces, target) {
301                return (target, Classification::Routed(source));
302            }
303
304            (target, Classification::Unmapped)
305        })
306        .collect();
307
308    for (target, class) in processed {
309        match class {
310            Classification::Local(idx) => local.entry(idx).or_default().insert(target),
311            Classification::Routed(source) => routed.push(RoutedTarget { target, source }),
312            Classification::Unmapped => unmapped.insert(target),
313            Classification::Ours => ours.insert(target),
314        }
315    }
316
317    // Withheld from every strategy. A range wholly inside a segment's subnet is
318    // assigned to that link without passing through the per-address check, so an
319    // address this host holds can arrive here inside a set.
320    for address in &owned_ips {
321        let mut one = IpSet::new();
322        one.insert(*address);
323
324        for targets in local.values_mut() {
325            if targets.contains(address) {
326                targets.subtract(&one);
327                ours.insert(*address);
328            }
329        }
330    }
331    // A link whose only target was ours has nothing left to sweep.
332    local.retain(|_, targets| !targets.is_empty());
333
334    let local = local
335        .into_iter()
336        .map(|(idx, ips)| (interfaces[idx].clone(), ips))
337        .collect();
338
339    RoutedTargets {
340        local,
341        routed,
342        unmapped,
343        ours,
344        ambiguous,
345        unenumerable,
346    }
347}
348
349/// The addresses among `targets`, on `link`'s segment, that this host's
350/// routing table refuses.
351///
352/// Frames built for a neighbour never ask the table, so a route an
353/// administrator added over one address of a connected prefix, or a VPN kill
354/// switch keeping the local network out, is heard only by asking. Every other
355/// program on the machine honours it, and a sweep should too.
356///
357/// Asked address by address: a route lookup each, no packet. Not asked: a
358/// link-local address (on its zone's segment by definition), a range too large
359/// to walk, and the network and broadcast addresses of the link's own prefixes,
360/// which a kernel refuses on other grounds.
361pub(crate) fn refused_neighbours(link: &Link, targets: &IpSet) -> IpSet {
362    refused_neighbours_asking(link, targets, refuses_neighbour)
363}
364
365/// [`refused_neighbours`], asking the table through `refuses`, for a test that
366/// needs the table to refuse as no test host does.
367fn refused_neighbours_asking(link: &Link, targets: &IpSet, refuses: fn(IpAddr) -> bool) -> IpSet {
368    let edges: HashSet<IpAddr> = link
369        .addresses()
370        .iter()
371        .filter_map(|held| match held.network() {
372            IpRange::V4(range) => Some([range.start_addr(), range.end_addr()]),
373            IpRange::V6(_) => None,
374        })
375        .flatten()
376        .map(IpAddr::V4)
377        .collect();
378    let v4 = targets.v4().iter().flat_map(Ipv4Range::iter);
379    let v6 = targets
380        .v6()
381        .iter()
382        .filter(|range| range.zone().is_none() && is_enumerable(range))
383        .flat_map(Ipv6Range::iter);
384    let walked = v4.chain(v6);
385
386    let refused: Vec<IpAddr> = walked
387        .filter(|target| !edges.contains(target) && !ScopedIp::needs_zone(target))
388        .par_bridge()
389        .map(|target| refuses(target).then_some(target))
390        .flatten()
391        .collect();
392
393    let mut set = IpSet::new();
394    for address in refused {
395        set.insert(address);
396    }
397    set.canonicalize();
398    set
399}
400
401/// Which of the engine's two frame builders a question about reach is asked for.
402///
403/// The segment sweep resolves an IPv6 neighbour itself, by neighbour discovery
404/// over the link it holds open. The probe transport's frame sender has only ARP,
405/// so it has no hardware address for an IPv6 neighbour.
406#[derive(Debug, Clone, Copy, PartialEq, Eq)]
407pub(crate) enum FrameSender {
408    /// ARP and ICMPv6 across a segment, which is discovery's local step.
409    Sweep,
410    /// The probe transport's frames: port probes, routed discovery, and every
411    /// later pass that sends its own segments to a host.
412    Probe,
413}
414
415/// Why a self-built frame cannot reach a target.
416#[derive(Debug, Clone, PartialEq, Eq)]
417pub(crate) enum Unframed {
418    /// The target is loopback.
419    Loopback,
420    /// The target is an address this host holds. Its kernel answers it through
421    /// loopback, so a frame put on a link for it reaches nobody who replies.
422    Ours,
423    /// The route to the target leaves by the named link, which carries no
424    /// frames: a tunnel, a VPN, or anything else without a hardware address
425    /// and a segment.
426    Tunnel(String),
427    /// Nothing routes to the target at all.
428    NoRoute,
429    /// The target is an IPv6 neighbour on the named link, and the probe
430    /// transport's sender has no neighbour discovery to resolve it with.
431    Neighbour(String),
432    /// The target is an IPv4 address written in the IPv4-mapped IPv6 block,
433    /// which only a socket can reach: no frame carries such an address.
434    Mapped,
435}
436
437/// A few words, for the brackets after the addresses a message lists.
438impl std::fmt::Display for Unframed {
439    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
440        match self {
441            Self::Loopback => f.write_str("loopback"),
442            Self::Ours => f.write_str("own address"),
443            Self::Tunnel(link) => write!(f, "via {link}"),
444            Self::NoRoute => f.write_str("no route"),
445            Self::Neighbour(link) => write!(f, "IPv6 neighbour on {link}, no NDP"),
446            Self::Mapped => f.write_str("IPv4-mapped"),
447        }
448    }
449}
450
451/// The targets a self-built frame cannot reach from this host, and why.
452///
453/// Built by [`beyond_frames`], for a process that may inject frames and holds
454/// nothing else: an unprivileged run on macOS with the BPF devices handed to a
455/// group, or any privileged run on Windows. Everything here needs a strategy
456/// that asks the kernel.
457#[derive(Debug, Default)]
458pub(crate) struct BeyondFrames {
459    /// Every target no frame reaches.
460    pub(crate) targets: IpSet,
461    /// Each reason that applied and the targets it applied to, in a fixed
462    /// order, none of them empty.
463    reasons: Vec<(Unframed, IpSet)>,
464}
465
466impl BeyondFrames {
467    /// Whether every target is within a frame's reach.
468    pub(crate) fn is_empty(&self) -> bool {
469        self.targets.is_empty()
470    }
471
472    /// Each reason with the lowest address it applied to and how many it
473    /// covered, for a message about the set.
474    pub(crate) fn summary(&self) -> Vec<(Unframed, IpAddr, u128)> {
475        self.reasons
476            .iter()
477            .filter_map(|(reason, targets)| {
478                let first = targets.iter().next()?;
479                Some((reason.clone(), first, targets.len()))
480            })
481            .collect()
482    }
483
484    /// Whether a connect to these targets is a fallback rather than their
485    /// route: some lie behind a tunnel, are IPv6 neighbours the sender cannot
486    /// resolve, or have no route at all.
487    ///
488    /// Root reaches the first two by raw socket, and nothing reaches the third,
489    /// so a run probing them by connect is weaker than one that could frame
490    /// them. Loopback, this host's own addresses and IPv4-mapped targets are
491    /// reached by a socket at any privilege, so connect loses nothing there.
492    pub(crate) fn is_a_fallback(&self) -> bool {
493        self.reasons.iter().any(|(reason, _)| {
494            matches!(
495                reason,
496                Unframed::Tunnel(_) | Unframed::Neighbour(_) | Unframed::NoRoute
497            )
498        })
499    }
500
501    /// Each reason that applied, in order, joined for the brackets after a
502    /// message line.
503    pub(crate) fn reasons(&self) -> String {
504        let named: Vec<String> = self
505            .reasons
506            .iter()
507            .map(|(reason, _)| reason.to_string())
508            .collect();
509        named.join(", ")
510    }
511
512    /// These, together with every address of `unmapped` they do not already
513    /// hold, each under the reason nothing routes a frame to it.
514    ///
515    /// For a phase whose connect step holds both what a frame cannot reach and
516    /// what the routing table left without a route, loopback included. The
517    /// second is classified from the address alone, since the routing table has
518    /// already been asked.
519    pub(crate) fn and_unmapped(mut self, unmapped: &IpSet) -> Self {
520        let mut rest = unmapped.clone();
521        rest.subtract(&self.targets);
522        for (reason, targets) in unmapped_reasons(rest) {
523            self.note(reason, targets);
524        }
525        self.targets.canonicalize();
526        self
527    }
528
529    /// One reason and the addresses it covers, joined to those it already
530    /// covers where it has been noted before.
531    fn note(&mut self, reason: Unframed, mut targets: IpSet) {
532        targets.canonicalize();
533        if targets.is_empty() {
534            return;
535        }
536        extend(&mut self.targets, &targets);
537        match self.reasons.iter_mut().find(|(held, _)| *held == reason) {
538            Some((_, held)) => {
539                extend(held, &targets);
540                held.canonicalize();
541            }
542            None => self.reasons.push((reason, targets)),
543        }
544    }
545}
546
547/// Why no frame reaches each of `unmapped`, addresses the routing table found
548/// no link for, split by reason: loopback, IPv4-mapped, and no route.
549///
550/// Split by block, since an unrouted range can be as wide as the target list.
551/// Loopback is `127.0.0.0/8` and `::1`, as [`IpAddr::is_loopback`] has it; an
552/// IPv4 loopback address written in the mapped block counts as mapped.
553fn unmapped_reasons(unmapped: IpSet) -> Vec<(Unframed, IpSet)> {
554    let block = |ranges: &[IpRange]| {
555        let mut set = IpSet::new();
556        for range in ranges {
557            set.insert_range(*range);
558        }
559        set
560    };
561    let v4 = |start: [u8; 4], end: [u8; 4]| {
562        V4(Ipv4Range::new(start.into(), end.into()).expect("an ordered range"))
563    };
564    let v6 = |start: u128, end: u128| {
565        V6(Ipv6Range::new(start.into(), end.into()).expect("an ordered range"))
566    };
567    let blocks = [
568        (
569            Unframed::Loopback,
570            block(&[v4([127, 0, 0, 0], [127, 255, 255, 255]), v6(1, 1)]),
571        ),
572        (
573            Unframed::Mapped,
574            block(&[v6(0xffff_0000_0000, 0xffff_ffff_ffff)]),
575        ),
576    ];
577
578    let mut reasons = Vec::new();
579    let mut rest = unmapped;
580    for (reason, block) in blocks {
581        let mut outside = rest.clone();
582        outside.subtract(&block);
583        let mut inside = rest;
584        inside.subtract(&outside);
585        reasons.push((reason, inside));
586        rest = outside;
587    }
588    reasons.push((Unframed::NoRoute, rest));
589    reasons.retain(|(_, targets)| !targets.is_empty());
590    reasons
591}
592
593/// Whether `target` is an IPv4 address written in the IPv4-mapped IPv6 block,
594/// `::ffff:0:0/96`.
595fn is_ipv4_mapped(target: IpAddr) -> bool {
596    matches!(target, IpAddr::V6(v6) if v6.to_ipv4_mapped().is_some())
597}
598
599/// Adds every range of `from` to `into`, leaving the merge to whoever reads it.
600fn extend(into: &mut IpSet, from: &IpSet) {
601    for range in from.v4() {
602        into.push_v4_range(*range);
603    }
604    for range in from.v6() {
605        into.push_v6_range(*range);
606    }
607}
608
609/// Which of `ip_set` a frame built by `sender` cannot reach from this host.
610///
611/// Classified as [`map_ips_to_interfaces_forced`] classifies: a routed target
612/// is out of reach when the source the kernel would send it from belongs to a
613/// link that carries no frames. The frame sender's own choice of egress is not
614/// consulted, since its reach is what is in question.
615pub(crate) fn beyond_frames(ip_set: IpSet, forced: &[IpAddr], sender: FrameSender) -> BeyondFrames {
616    beyond_frames_with(ip_set, viable_interfaces(), forced, sender)
617}
618
619/// [`beyond_frames`] against an interface table the caller supplies, the seam
620/// its decisions are tested through.
621pub(crate) fn beyond_frames_with(
622    ip_set: IpSet,
623    interfaces: Vec<Link>,
624    forced: &[IpAddr],
625    sender: FrameSender,
626) -> BeyondFrames {
627    let links = interfaces.clone();
628    let RoutedTargets {
629        local,
630        routed,
631        unmapped,
632        ours,
633        ..
634    } = map_ips_to_interfaces_with(ip_set, interfaces, forced);
635
636    // Grouped by reason before counting, since one tunnel can hold targets on
637    // its own subnet and targets routed through it.
638    let mut groups: Vec<(Unframed, IpSet)> = Vec::new();
639    let mut add = |reason: Unframed, range: IpRange| match groups
640        .iter_mut()
641        .find(|(held, _)| *held == reason)
642    {
643        Some((_, targets)) => targets.insert_range(range),
644        None => {
645            let mut targets = IpSet::new();
646            targets.insert_range(range);
647            groups.push((reason, targets));
648        }
649    };
650
651    for (reason, targets) in unmapped_reasons(unmapped) {
652        for range in targets.v4() {
653            add(reason.clone(), V4(*range));
654        }
655        for range in targets.v6() {
656            add(reason.clone(), V6(*range));
657        }
658    }
659    for range in ours.v4() {
660        add(Unframed::Ours, V4(*range));
661    }
662    for range in ours.v6() {
663        add(Unframed::Ours, V6(*range));
664    }
665
666    // Sorted by name, for a stable message order.
667    let mut local: Vec<(Link, IpSet)> = local.into_iter().collect();
668    local.sort_by(|(a, _), (b, _)| a.name().cmp(b.name()));
669    for (link, targets) in &local {
670        // Only a link-local target whose zone named a tunnel is in `local` on a
671        // link without frames; a tunnel's own subnet is routed through it.
672        if !link.carries_frames() {
673            for range in targets.v4() {
674                add(Unframed::Tunnel(link.name().to_string()), V4(*range));
675            }
676            for range in targets.v6() {
677                add(Unframed::Tunnel(link.name().to_string()), V6(*range));
678            }
679        } else if sender == FrameSender::Probe {
680            for range in targets.v6() {
681                add(Unframed::Neighbour(link.name().to_string()), V6(*range));
682            }
683        }
684    }
685
686    for RoutedTarget { target, source } in routed {
687        // A source no link here holds is a forced address this host does not
688        // have. The frame sender builds that frame as asked, and a connect could
689        // not honour it, so it stays.
690        let Some(owner) = links
691            .iter()
692            .find(|link| link.addresses().iter().any(|held| held.address() == source))
693        else {
694            continue;
695        };
696        if !owner.carries_frames() {
697            add(Unframed::Tunnel(owner.name().to_string()), single(target));
698        }
699    }
700
701    let mut beyond = BeyondFrames::default();
702    for (reason, targets) in groups {
703        beyond.note(reason, targets);
704    }
705    beyond.targets.canonicalize();
706    beyond
707}
708
709/// One address as a range of itself.
710fn single(address: IpAddr) -> IpRange {
711    match address {
712        IpAddr::V4(v4) => V4(Ipv4Range::single(v4)),
713        IpAddr::V6(v6) => V6(Ipv6Range::single(v6)),
714    }
715}
716
717/// Whether an IPv6 range is small enough to probe one address at a time.
718///
719/// Asked of a range: a set holding a `/64` and three literals is partly
720/// walkable. See [`MAX_ENUMERABLE_ADDRESSES`].
721pub fn is_enumerable(range: &Ipv6Range) -> bool {
722    range.len() <= MAX_ENUMERABLE_ADDRESSES
723}
724
725/// The segment the whole inclusive range `[start, end]` is on, if it is on one.
726///
727/// Kept whole only where one link answers for every address in it, with no
728/// narrower prefix on another link inside the range (a VPN's `/24` within the
729/// LAN's `/8`, say). Otherwise each address asks [`holding_prefix`] for
730/// itself.
731///
732/// A host prefix (`/32`, `/128`) does not count: it covers only this host's own
733/// address, and Linux lists every DHCPv6 address as one, so splitting an
734/// on-link `/64` around it would refuse the segment as too large to walk.
735fn owning_interface(links: &[Link], start: IpAddr, end: IpAddr) -> Option<usize> {
736    let (idx, owner) = holding_prefix(links, start)?;
737    let narrower_inside = links
738        .iter()
739        .enumerate()
740        .filter(|(other, _)| *other != idx)
741        .flat_map(|(_, link)| link.addresses())
742        .filter(|held| held.prefix() > owner.prefix())
743        .map(|held| held.network())
744        .filter(|network| network.len() > 1)
745        .any(|network| {
746            let (low, high) = (network.start_addr(), network.end_addr());
747            low.is_ipv4() == start.is_ipv4() && low <= end && start <= high
748        });
749
750    (links[idx].carries_frames() && owner.contains(&end) && !narrower_inside).then_some(idx)
751}
752
753/// The interface holding the most specific prefix that contains `target`,
754/// and the address it holds there.
755///
756/// The kernel sends by the most specific connected route, so this does too: a
757/// VPN's `/24` inside a LAN's `/8` takes the targets in the `/24`. On a tie the
758/// first interface listed wins. Matching is within one address family.
759///
760/// On a link that carries frames the prefix is a segment, swept at the link
761/// layer. On a tunnel it is only a route: its peers (a WireGuard peer, an
762/// OpenVPN server in subnet topology) are probed through the tunnel from the
763/// tunnel's address, since nothing behind it answers ARP or neighbour
764/// discovery.
765fn holding_prefix(links: &[Link], target: IpAddr) -> Option<(usize, LinkAddress)> {
766    let mut best: Option<(usize, LinkAddress)> = None;
767    for (idx, link) in links.iter().enumerate() {
768        for held in link.addresses() {
769            if held.contains(&target) && best.is_none_or(|(_, b)| held.prefix() > b.prefix()) {
770                best = Some((idx, *held));
771            }
772        }
773    }
774    best
775}
776
777// ╔════════════════════════════════════════════╗
778// ║ ████████╗███████╗███████╗████████╗███████╗ ║
779// ║ ╚══██╔══╝██╔════╝██╔════╝╚══██╔══╝██╔════╝ ║
780// ║    ██║   █████╗  ███████╗   ██║   ███████╗ ║
781// ║    ██║   ██╔══╝  ╚════██║   ██║   ╚════██║ ║
782// ║    ██║   ███████╗███████║   ██║   ███████║ ║
783// ║    ╚═╝   ╚══════╝╚══════╝   ╚═╝   ╚══════╝ ║
784// ╚════════════════════════════════════════════╝
785
786#[cfg(test)]
787mod tests {
788    use super::*;
789    use crate::model::ip::range::{IpRange, Ipv4Range, Ipv6Range};
790    use crate::model::mac::MacAddr;
791    use std::net::{Ipv4Addr, Ipv6Addr};
792
793    /// An Ethernet interface holding one address.
794    fn mock_named(name: &str, index: u32, ip: IpAddr, prefix: u8) -> Link {
795        Link::new(name, index)
796            .with_mac(MacAddr::new(0x02, 0, 0, 0, 0, index as u8))
797            .with_addressing(crate::system::interface::Addressing::Broadcast)
798            .with_addresses(vec![crate::system::interface::LinkAddress::new(ip, prefix)])
799    }
800
801    fn mock_interface(ip: IpAddr, prefix: u8) -> Link {
802        mock_named("test0", 0, ip, prefix)
803    }
804
805    #[test]
806    fn the_interface_holding_a_targets_prefix_is_found() {
807        let interfaces = vec![
808            mock_interface(IpAddr::V4(Ipv4Addr::new(192, 0, 2, 100)), 24),
809            mock_interface(IpAddr::V4(Ipv4Addr::new(198, 51, 100, 5)), 24),
810        ];
811        let holder = |target: [u8; 4]| {
812            holding_prefix(&interfaces, IpAddr::V4(Ipv4Addr::from(target))).map(|(idx, _)| idx)
813        };
814
815        assert_eq!(holder([192, 0, 2, 50]), Some(0));
816        assert_eq!(holder([198, 51, 100, 200]), Some(1));
817        assert_eq!(holder([203, 0, 113, 1]), None, "held by neither");
818    }
819
820    /// A routed target whose route refuses by policy is given to no raw strategy,
821    /// forced source or fallback source; the connect fallback meets the same
822    /// refusal as the rest of the machine. A missing route still gets the
823    /// fallback.
824    #[test]
825    fn a_routed_target_a_route_forbids_is_left_to_the_connect_fallback() {
826        let global = IpAddr::V6(Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, 5));
827        let lan = IpAddr::V4(Ipv4Addr::new(192, 0, 2, 1));
828        let interfaces = || vec![mock_interface(global, 64), mock_interface(lan, 24)];
829        let v6 = IpAddr::V6(Ipv6Addr::new(0x2001, 0xdb8, 9, 0, 0, 0, 0, 1));
830        let v4 = IpAddr::V4(Ipv4Addr::new(203, 0, 113, 1));
831        let targets = || {
832            let mut set = IpSet::new();
833            set.insert(v6);
834            set.insert(v4);
835            set
836        };
837
838        let forbidden = map_ips_to_interfaces_asking(targets(), interfaces(), &[lan], |_| {
839            RouteAnswer::Forbidden
840        });
841        assert!(forbidden.routed.is_empty(), "{:?}", forbidden.routed);
842        assert!(forbidden.unmapped.contains(&v6) && forbidden.unmapped.contains(&v4));
843
844        let missing =
845            map_ips_to_interfaces_asking(targets(), interfaces(), &[], |_| RouteAnswer::NoRoute);
846        assert!(
847            missing
848                .routed
849                .iter()
850                .any(|routed| routed.target == v6 && routed.source == global),
851            "{:?}",
852            missing.routed
853        );
854    }
855
856    /// A neighbour the routing table refuses is found among a segment's targets,
857    /// walked or named, and nothing else is: not its neighbours, not the
858    /// segment's network and broadcast addresses, and not a link-local address.
859    #[test]
860    fn a_neighbour_the_routing_table_refuses_is_told_apart_from_the_segment() {
861        let link = mock_interface(IpAddr::V4(Ipv4Addr::new(192, 0, 2, 1)), 24);
862        let mut targets = IpSet::new();
863        targets.insert_range(IpRange::V4(
864            Ipv4Range::new(Ipv4Addr::new(192, 0, 2, 0), Ipv4Addr::new(192, 0, 2, 255)).unwrap(),
865        ));
866        targets.insert(IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 13)));
867        targets.insert(IpAddr::V6(Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, 13)));
868
869        // Refuses every address whose last group is 13, and the segment's
870        // edges, as a kernel refuses a broadcast.
871        let refused = refused_neighbours_asking(&link, &targets, |target| match target {
872            IpAddr::V4(v4) => matches!(v4.octets()[3], 0 | 13 | 255),
873            IpAddr::V6(v6) => v6.segments()[7] == 13,
874        });
875
876        let mut expected = IpSet::new();
877        expected.insert(IpAddr::V4(Ipv4Addr::new(192, 0, 2, 13)));
878        expected.insert(IpAddr::V6(Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, 13)));
879        expected.canonicalize();
880        assert_eq!(refused, expected);
881    }
882
883    #[test]
884    fn on_link_v4_range_stays_intact_and_local() {
885        let interfaces = vec![mock_interface(IpAddr::V4(Ipv4Addr::new(192, 0, 2, 1)), 24)];
886        let mut set = IpSet::new();
887        set.insert_range(IpRange::V4(
888            Ipv4Range::new(Ipv4Addr::new(192, 0, 2, 10), Ipv4Addr::new(192, 0, 2, 20)).unwrap(),
889        ));
890
891        let result = map_ips_to_interfaces_with(set, interfaces, &[]);
892
893        assert!(result.routed.is_empty());
894        assert!(result.unmapped.is_empty());
895        assert_eq!(result.local.len(), 1);
896        let (_, ips) = result.local.into_iter().next().unwrap();
897        assert_eq!(ips.len(), 11);
898    }
899
900    /// The boundary of the enumeration ceiling, checked exactly, without
901    /// expanding a range: a `/112` is probed, a `/111` is not.
902    #[test]
903    fn the_enumeration_ceiling_is_a_112() {
904        let base = Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, 0);
905        let at_ceiling = Ipv6Range::new(base, Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, 0xffff));
906        let over_ceiling = Ipv6Range::new(base, Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 1, 0));
907
908        let at_ceiling = at_ceiling.unwrap();
909        assert_eq!(at_ceiling.len(), MAX_ENUMERABLE_ADDRESSES);
910        assert!(is_enumerable(&at_ceiling), "a /112 is 65536 addresses");
911        assert!(
912            !is_enumerable(&over_ceiling.unwrap()),
913            "one address more is not"
914        );
915    }
916
917    /// A routed `/64` expanded into a `Vec<IpAddr>` exhausts memory. It must
918    /// come out as its own category so the caller can tell it from a range with
919    /// nothing on it.
920    #[test]
921    fn a_routed_v6_prefix_too_large_to_walk_is_refused_rather_than_expanded() {
922        let interfaces = vec![mock_interface(IpAddr::V4(Ipv4Addr::new(192, 0, 2, 1)), 24)];
923        let mut set = IpSet::new();
924        set.insert_range(IpRange::V6(
925            Ipv6Range::new(
926                Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, 0),
927                Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0xffff, 0xffff, 0xffff, 0xffff),
928            )
929            .unwrap(),
930        ));
931
932        let result = map_ips_to_interfaces_with(set, interfaces, &[]);
933
934        assert_eq!(result.unenumerable.len(), 1, "the /64 is reported whole");
935        assert!(result.routed.is_empty());
936        assert!(result.unmapped.is_empty());
937        assert!(result.local.is_empty());
938    }
939
940    /// Every interface holds an `fe80::/64`, so a bare link-local target matches
941    /// all of them, and `owning_interface` would return whichever the host listed
942    /// first.
943    #[test]
944    fn a_link_local_target_naming_no_interface_is_refused() {
945        let link_local = Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 0xAA);
946        let interfaces = vec![
947            mock_interface(IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 1)), 64),
948            mock_interface(IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 2)), 64),
949        ];
950        let mut set = IpSet::new();
951        set.insert(IpAddr::V6(link_local));
952
953        let result = map_ips_to_interfaces_with(set, interfaces, &[]);
954
955        assert_eq!(result.ambiguous.len(), 1);
956        assert!(
957            result.local.is_empty(),
958            "guessing an interface is what this prevents"
959        );
960    }
961
962    /// Named, the same target is unambiguous, and the name outranks any prefix
963    /// match.
964    #[test]
965    fn a_link_local_target_goes_to_the_interface_it_names() {
966        let link_local = Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 0xAA);
967        let first = mock_named(
968            "en3",
969            3,
970            IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 1)),
971            64,
972        );
973        let second = mock_named(
974            "en9",
975            9,
976            IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 2)),
977            64,
978        );
979
980        let mut set = IpSet::new();
981        set.insert_range(IpRange::V6(
982            Ipv6Range::scoped(link_local, link_local, Some(9)).unwrap(),
983        ));
984
985        let result = map_ips_to_interfaces_with(set, vec![first, second], &[]);
986
987        assert!(result.ambiguous.is_empty());
988        assert_eq!(result.local.len(), 1);
989        let (intf, ips) = result.local.into_iter().next().unwrap();
990        assert_eq!(intf.name(), "en9", "the second interface was the one named");
991        assert_eq!(ips.len(), 1);
992    }
993
994    #[test]
995    fn on_link_v6_range_is_classified_local() {
996        let base = Ipv6Addr::new(0xfd00, 0, 0, 0, 0, 0, 0, 0);
997        let interfaces = vec![mock_interface(IpAddr::V6(base), 64)];
998        let mut set = IpSet::new();
999        set.insert_range(IpRange::V6(
1000            Ipv6Range::new(
1001                Ipv6Addr::new(0xfd00, 0, 0, 0, 0, 0, 0, 1),
1002                Ipv6Addr::new(0xfd00, 0, 0, 0, 0, 0, 0, 5),
1003            )
1004            .unwrap(),
1005        ));
1006
1007        let result = map_ips_to_interfaces_with(set, interfaces, &[]);
1008
1009        assert!(result.routed.is_empty());
1010        assert!(result.unmapped.is_empty());
1011        assert_eq!(result.local.len(), 1);
1012        let (_, ips) = result.local.into_iter().next().unwrap();
1013        assert_eq!(ips.len(), 5);
1014    }
1015
1016    /// This host's own LAN address sits inside its interface's subnet, so the
1017    /// on-link test claims it, but no probe can establish it because the kernel
1018    /// routes it through loopback.
1019    #[test]
1020    fn an_address_this_host_holds_is_ours_rather_than_on_link() {
1021        let own: IpAddr = "203.0.113.160".parse().unwrap();
1022        let interfaces = vec![mock_interface(own, 24)];
1023
1024        let mut targets = IpSet::new();
1025        targets.insert(own);
1026
1027        let routed = map_ips_to_interfaces_with(targets, interfaces, &[]);
1028
1029        assert!(routed.ours.contains(&own), "the address is this host's own");
1030        assert!(
1031            routed.local.is_empty(),
1032            "and must not be handed to a link-layer strategy"
1033        );
1034    }
1035
1036    /// A neighbour on the same segment still gets the on-link strategy.
1037    #[test]
1038    fn a_neighbour_on_the_same_segment_is_still_on_link() {
1039        let own: IpAddr = "203.0.113.160".parse().unwrap();
1040        let neighbour: IpAddr = "203.0.113.101".parse().unwrap();
1041        let interfaces = vec![mock_interface(own, 24)];
1042
1043        let mut targets = IpSet::new();
1044        targets.insert(neighbour);
1045
1046        let routed = map_ips_to_interfaces_with(targets, interfaces, &[]);
1047
1048        assert!(routed.ours.is_empty());
1049        assert_eq!(
1050            routed.local.values().next().map(IpSet::len),
1051            Some(1u128),
1052            "the neighbour is on-link"
1053        );
1054    }
1055
1056    /// A link a frame can be put on: a hardware address and a segment.
1057    fn ethernet(addresses: &[(&str, u8)]) -> Link {
1058        Link::new("en0", 4)
1059            .with_mac(crate::model::mac::MacAddr::new(0x02, 0, 0, 0, 0, 0x10))
1060            .with_kind(crate::system::interface::LinkKind::Wired)
1061            .with_addressing(crate::system::interface::Addressing::Broadcast)
1062            .with_link_up(true)
1063            .with_addresses(held(addresses))
1064    }
1065
1066    /// A VPN's tunnel, as macOS presents one: a peer and no segment, and no
1067    /// hardware address.
1068    fn tunnel(addresses: &[(&str, u8)]) -> Link {
1069        Link::new("utun9", 20)
1070            .with_addressing(crate::system::interface::Addressing::PointToPoint)
1071            .with_link_up(true)
1072            .with_addresses(held(addresses))
1073    }
1074
1075    fn held(addresses: &[(&str, u8)]) -> Vec<crate::system::interface::LinkAddress> {
1076        addresses
1077            .iter()
1078            .map(|(address, prefix)| {
1079                crate::system::interface::LinkAddress::new(
1080                    address.parse().expect("a literal"),
1081                    *prefix,
1082                )
1083            })
1084            .collect()
1085    }
1086
1087    fn set_of(addresses: &[&str]) -> IpSet {
1088        let mut set = IpSet::new();
1089        for address in addresses {
1090            set.insert(address.parse().expect("a literal"));
1091        }
1092        set
1093    }
1094
1095    fn ip(literal: &str) -> IpAddr {
1096        literal.parse().expect("a literal")
1097    }
1098
1099    /// Without its own check, `::1` would be classified as a routed target with
1100    /// a global source: the kernel answers it from `::1`, no viable interface
1101    /// holds that, and the VPN fallback offers the first global address.
1102    /// `127.0.0.1` would be spared only because the fallback declines IPv4. A
1103    /// forced source would do the same to both.
1104    #[test]
1105    fn loopback_is_unmapped_in_both_families_whatever_is_forced() {
1106        let interfaces = vec![ethernet(&[("192.0.2.10", 24), ("2001:db8:1::10", 64)])];
1107        let forced = [ip("192.0.2.10"), ip("2001:db8:1::10")];
1108
1109        for forced in [&forced[..], &[]] {
1110            let routed = map_ips_to_interfaces_with(
1111                set_of(&["127.0.0.1", "::1"]),
1112                interfaces.clone(),
1113                forced,
1114            );
1115
1116            assert!(
1117                routed.routed.is_empty(),
1118                "loopback is not behind a gateway: {:?}",
1119                routed.routed
1120            );
1121            assert!(routed.unmapped.contains(&ip("127.0.0.1")));
1122            assert!(routed.unmapped.contains(&ip("::1")));
1123        }
1124    }
1125
1126    /// An IPv4-mapped address is an IPv4 host no frame can carry, so it is never
1127    /// paired with an IPv6 source and framed toward the router, whatever source
1128    /// is forced and whatever global address the host holds.
1129    #[test]
1130    fn a_mapped_address_is_unmapped_whatever_is_forced() {
1131        let interfaces = vec![ethernet(&[("192.0.2.10", 24), ("2001:db8:1::10", 64)])];
1132        let forced = [ip("192.0.2.10"), ip("2001:db8:1::10")];
1133
1134        for forced in [&forced[..], &[]] {
1135            let routed = map_ips_to_interfaces_with(
1136                set_of(&["::ffff:127.0.0.1", "::ffff:198.51.100.7"]),
1137                interfaces.clone(),
1138                forced,
1139            );
1140
1141            assert!(
1142                routed.routed.is_empty(),
1143                "a mapped address is not behind a gateway: {:?}",
1144                routed.routed
1145            );
1146            assert!(routed.unmapped.contains(&ip("::ffff:127.0.0.1")));
1147            assert!(routed.unmapped.contains(&ip("::ffff:198.51.100.7")));
1148        }
1149    }
1150
1151    /// And a frames-only run says why it reaches one by connect.
1152    #[test]
1153    fn a_mapped_address_is_beyond_frames_as_what_it_is() {
1154        let beyond = beyond_frames_with(
1155            set_of(&["::ffff:198.51.100.7"]),
1156            vec![ethernet(&[("192.0.2.10", 24), ("2001:db8:1::10", 64)])],
1157            &[],
1158            FrameSender::Probe,
1159        );
1160
1161        assert_eq!(
1162            beyond.summary(),
1163            vec![(Unframed::Mapped, ip("::ffff:198.51.100.7"), 1)]
1164        );
1165    }
1166
1167    /// A connect step holds what a frame cannot reach and what no route leads
1168    /// to, and names each address for what it is: loopback, mapped (whichever
1169    /// block it was written in), or no route. An address already held keeps its
1170    /// reason.
1171    #[test]
1172    fn what_no_route_leads_to_is_named_for_what_it_is() {
1173        let held = beyond_frames_with(
1174            set_of(&["::ffff:198.51.100.7"]),
1175            vec![ethernet(&[("192.0.2.10", 24), ("2001:db8:1::10", 64)])],
1176            &[],
1177            FrameSender::Probe,
1178        );
1179
1180        let all = held.and_unmapped(&set_of(&[
1181            "::ffff:198.51.100.7",
1182            "127.0.0.2",
1183            "::1",
1184            "::ffff:127.0.0.1",
1185            "203.0.113.9",
1186            "203.0.113.10",
1187        ]));
1188
1189        assert_eq!(
1190            all.summary(),
1191            vec![
1192                (Unframed::Mapped, ip("::ffff:127.0.0.1"), 2),
1193                (Unframed::Loopback, ip("127.0.0.2"), 2),
1194                (Unframed::NoRoute, ip("203.0.113.9"), 2),
1195            ]
1196        );
1197        assert_eq!(all.targets.len(), 6);
1198    }
1199
1200    /// What a frame reaches: a neighbour it can ARP for, and a routed target
1201    /// whose route leaves by a link with Ethernet in front of it.
1202    #[test]
1203    fn a_frame_reaches_an_ipv4_neighbour_and_a_target_routed_over_ethernet() {
1204        let beyond = beyond_frames_with(
1205            set_of(&["192.0.2.50", "203.0.113.9"]),
1206            vec![ethernet(&[("192.0.2.10", 24)])],
1207            &[ip("192.0.2.10")],
1208            FrameSender::Probe,
1209        );
1210
1211        assert!(beyond.is_empty(), "nothing out of reach: {beyond:?}");
1212    }
1213
1214    /// The kernel sends the target from the tunnel's address, so its route
1215    /// leaves by a link no frame can be put on.
1216    #[test]
1217    fn a_target_routed_through_a_tunnel_is_beyond_frames() {
1218        let beyond = beyond_frames_with(
1219            set_of(&["203.0.113.23"]),
1220            vec![
1221                ethernet(&[("192.0.2.10", 24)]),
1222                tunnel(&[("198.51.100.2", 32)]),
1223            ],
1224            &[ip("198.51.100.2")],
1225            FrameSender::Sweep,
1226        );
1227
1228        assert!(beyond.targets.contains(&ip("203.0.113.23")));
1229        assert_eq!(
1230            beyond.summary(),
1231            vec![(Unframed::Tunnel("utun9".into()), ip("203.0.113.23"), 1)]
1232        );
1233        assert!(beyond.is_a_fallback(), "a raw socket reaches it");
1234    }
1235
1236    /// A tunnel's own subnet is not a segment. Its subnet and a target routed
1237    /// through it are one reason, counted once.
1238    #[test]
1239    fn a_tunnels_own_subnet_is_beyond_frames_under_the_same_reason() {
1240        let beyond = beyond_frames_with(
1241            set_of(&["198.51.100.7", "203.0.113.23"]),
1242            vec![tunnel(&[("198.51.100.2", 24)])],
1243            &[ip("198.51.100.2")],
1244            FrameSender::Sweep,
1245        );
1246
1247        assert_eq!(beyond.targets.len(), 2);
1248        assert_eq!(
1249            beyond.summary(),
1250            vec![(Unframed::Tunnel("utun9".into()), ip("198.51.100.7"), 2)]
1251        );
1252    }
1253
1254    /// A WireGuard peer, or an OpenVPN server in subnet topology, sits inside
1255    /// the prefix the tunnel's own address carries, and is probed through the
1256    /// tunnel from the tunnel's address, as the kernel would send to it.
1257    #[test]
1258    fn a_host_on_a_tunnels_own_subnet_is_routed_through_the_tunnel() {
1259        let interfaces = vec![
1260            ethernet(&[("192.0.2.10", 24)]),
1261            tunnel(&[("198.51.100.2", 24), ("2001:db8:66::2", 64)]),
1262        ];
1263
1264        let routed = map_ips_to_interfaces_with(
1265            set_of(&["198.51.100.1", "2001:db8:66::1"]),
1266            interfaces,
1267            &[],
1268        );
1269
1270        assert!(
1271            routed.local.is_empty(),
1272            "a tunnel has no segment to sweep: {:?}",
1273            routed.local
1274        );
1275        assert_eq!(
1276            routed.routed,
1277            vec![
1278                RoutedTarget {
1279                    target: ip("198.51.100.1"),
1280                    source: ip("198.51.100.2"),
1281                },
1282                RoutedTarget {
1283                    target: ip("2001:db8:66::1"),
1284                    source: ip("2001:db8:66::2"),
1285                },
1286            ]
1287        );
1288    }
1289
1290    /// A peer on the tunnel's own subnet is reached only through that tunnel,
1291    /// so a forced source does not apply and it keeps the tunnel's address.
1292    #[test]
1293    fn a_forced_source_does_not_take_a_host_off_its_tunnels_subnet() {
1294        let routed = map_ips_to_interfaces_with(
1295            set_of(&["198.51.100.1"]),
1296            vec![
1297                ethernet(&[("192.0.2.10", 24)]),
1298                tunnel(&[("198.51.100.2", 24)]),
1299            ],
1300            &[ip("192.0.2.10")],
1301        );
1302
1303        assert_eq!(
1304            routed.routed,
1305            vec![RoutedTarget {
1306                target: ip("198.51.100.1"),
1307                source: ip("198.51.100.2"),
1308            }]
1309        );
1310    }
1311
1312    /// A sweep of the tunnel's whole subnet is a list of peers to probe through
1313    /// it, less the tunnel's own address, which is this host's.
1314    #[test]
1315    fn a_tunnels_subnet_as_a_range_is_routed_address_by_address() {
1316        let mut targets = IpSet::new();
1317        targets.insert_range(V4(Ipv4Range::new(
1318            "198.51.100.0".parse().unwrap(),
1319            "198.51.100.3".parse().unwrap(),
1320        )
1321        .expect("an ordered range")));
1322
1323        let routed =
1324            map_ips_to_interfaces_with(targets, vec![tunnel(&[("198.51.100.2", 24)])], &[]);
1325
1326        assert!(routed.local.is_empty(), "{:?}", routed.local);
1327        let probed: Vec<IpAddr> = routed.routed.iter().map(|r| r.target).collect();
1328        assert_eq!(
1329            probed,
1330            ["198.51.100.0", "198.51.100.1", "198.51.100.3"].map(ip)
1331        );
1332        assert!(routed.routed.iter().all(|r| r.source == ip("198.51.100.2")));
1333        assert!(routed.ours.contains(&ip("198.51.100.2")));
1334        assert_eq!(routed.ours.len(), 1);
1335    }
1336
1337    /// Prefixes nest, and the most specific one is the route, as in the kernel:
1338    /// a VPN's prefix inside the LAN's takes its own targets, and a LAN inside a
1339    /// tunnel's wider prefix keeps its neighbours.
1340    #[test]
1341    fn the_most_specific_prefix_decides_between_a_segment_and_a_tunnel() {
1342        let interfaces = vec![
1343            ethernet(&[("198.51.100.10", 24), ("2001:db8:0:1::10", 64)]),
1344            tunnel(&[("198.51.100.130", 25), ("2001:db8::2", 40)]),
1345        ];
1346
1347        let routed = map_ips_to_interfaces_with(
1348            set_of(&[
1349                "198.51.100.7",
1350                "198.51.100.200",
1351                "2001:db8:0:1::20",
1352                "2001:db8:5::1",
1353            ]),
1354            interfaces,
1355            &[],
1356        );
1357
1358        let swept: Vec<IpAddr> = routed.local.values().flat_map(IpSet::iter).collect();
1359        assert_eq!(swept, ["198.51.100.7", "2001:db8:0:1::20"].map(ip));
1360        assert_eq!(
1361            routed.routed,
1362            vec![
1363                RoutedTarget {
1364                    target: ip("198.51.100.200"),
1365                    source: ip("198.51.100.130"),
1366                },
1367                RoutedTarget {
1368                    target: ip("2001:db8:5::1"),
1369                    source: ip("2001:db8::2"),
1370                },
1371            ]
1372        );
1373    }
1374
1375    /// A segment's range stays whole around a host prefix, on its own link or
1376    /// on a tunnel.
1377    #[test]
1378    fn a_host_prefix_inside_a_segments_range_leaves_the_range_whole() {
1379        let mut lan = ethernet(&[("2001:db8:1::10", 64)]);
1380        lan = lan.with_addresses(held(&[("2001:db8:1::10", 64), ("2001:db8:1::abcd", 128)]));
1381        let interfaces = vec![lan, tunnel(&[("2001:db8:1::99", 128)])];
1382
1383        let mut targets = IpSet::new();
1384        targets.insert_range(V6(Ipv6Range::new(
1385            "2001:db8:1::".parse().unwrap(),
1386            "2001:db8:1::ffff:ffff:ffff:ffff".parse().unwrap(),
1387        )
1388        .expect("an ordered range")));
1389
1390        let routed = map_ips_to_interfaces_with(targets, interfaces, &[]);
1391
1392        assert!(routed.unenumerable.is_empty(), "{:?}", routed.unenumerable);
1393        assert_eq!(routed.local.len(), 1, "the /64 is swept on its segment");
1394    }
1395
1396    /// The segment sweep resolves an IPv6 neighbour itself; the probe sender
1397    /// has only ARP.
1398    #[test]
1399    fn an_ipv6_neighbour_is_within_the_sweep_and_beyond_the_probe_sender() {
1400        let interfaces = vec![ethernet(&[("192.0.2.10", 24), ("2001:db8:1::10", 64)])];
1401        let targets = set_of(&["2001:db8:1::20", "192.0.2.50"]);
1402
1403        let swept =
1404            beyond_frames_with(targets.clone(), interfaces.clone(), &[], FrameSender::Sweep);
1405        assert!(swept.is_empty(), "the sweep reaches both: {swept:?}");
1406
1407        let probed = beyond_frames_with(targets, interfaces, &[], FrameSender::Probe);
1408        assert_eq!(
1409            probed.summary(),
1410            vec![(Unframed::Neighbour("en0".into()), ip("2001:db8:1::20"), 1)],
1411            "and the probe sender only the IPv4 one"
1412        );
1413    }
1414
1415    /// The kernel answers these itself, so a frame for either reaches nobody who
1416    /// replies. Two reasons, in the order a message names them.
1417    #[test]
1418    fn loopback_and_this_hosts_own_addresses_are_beyond_frames() {
1419        let beyond = beyond_frames_with(
1420            set_of(&["127.0.0.1", "::1", "192.0.2.10"]),
1421            vec![ethernet(&[("192.0.2.10", 24)])],
1422            &[],
1423            FrameSender::Probe,
1424        );
1425
1426        assert_eq!(
1427            beyond.summary(),
1428            vec![
1429                (Unframed::Loopback, ip("127.0.0.1"), 2),
1430                (Unframed::Ours, ip("192.0.2.10"), 1),
1431            ]
1432        );
1433        assert!(!beyond.is_a_fallback(), "connect is their route");
1434    }
1435
1436    /// One address behind a tunnel makes the whole set a fallback, however
1437    /// many others are this host's own: a segment routed into a VPN holds the
1438    /// host's address and every other address through the tunnel.
1439    #[test]
1440    fn one_tunnelled_target_makes_a_connect_a_fallback() {
1441        let mut beyond = BeyondFrames::default();
1442        beyond.note(Unframed::Ours, set_of(&["192.0.2.10"]));
1443        assert!(!beyond.is_a_fallback());
1444
1445        beyond.note(Unframed::Tunnel("utun9".into()), set_of(&["192.0.2.11"]));
1446        assert!(beyond.is_a_fallback());
1447        assert_eq!(beyond.reasons(), "own address, via utun9");
1448    }
1449
1450    /// A routed target the kernel would send from the tunnel is sent from the
1451    /// forced LAN source, and the routing table is never asked: the source is
1452    /// picked by family.
1453    #[test]
1454    fn a_forced_source_outranks_the_routing_table_for_a_routed_target() {
1455        let lan: IpAddr = "203.0.113.160".parse().unwrap();
1456        let public: IpAddr = "1.1.1.1".parse().unwrap();
1457        let interfaces = vec![mock_interface(lan, 24)];
1458
1459        let mut targets = IpSet::new();
1460        targets.insert(public);
1461
1462        let routed = map_ips_to_interfaces_with(targets, interfaces, &[lan]);
1463
1464        assert_eq!(
1465            routed.routed,
1466            vec![RoutedTarget {
1467                target: public,
1468                source: lan
1469            }],
1470            "the off-link target is probed from the forced source"
1471        );
1472    }
1473}