use crate::model::ip::range::IpRange::{self, V4, V6};
use crate::model::ip::range::{Ipv4Range, Ipv6Range};
use crate::model::ip::set::IpSet;
use crate::system::interface::Link;
use crate::system::interface::source::{
ProbeSockets, plausible_source, probe_route_source, viable_interfaces,
};
use rayon::prelude::*;
use std::collections::{HashMap, HashSet};
use std::net::IpAddr;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RoutedTarget {
pub target: IpAddr,
pub source: IpAddr,
}
pub const MAX_ENUMERABLE_ADDRESSES: u128 = 1 << 16;
#[derive(Debug, Default)]
pub struct RoutedTargets {
pub local: HashMap<Link, IpSet>,
pub routed: Vec<RoutedTarget>,
pub unmapped: IpSet,
pub ours: IpSet,
pub ambiguous: Vec<Ipv6Range>,
pub unenumerable: Vec<Ipv6Range>,
}
pub fn map_ips_to_interfaces(ip_set: IpSet) -> RoutedTargets {
map_ips_to_interfaces_with(ip_set, viable_interfaces(), &[])
}
pub(crate) fn map_ips_to_interfaces_forced(ip_set: IpSet, forced: &[IpAddr]) -> RoutedTargets {
map_ips_to_interfaces_with(ip_set, viable_interfaces(), forced)
}
enum Classification {
Local(usize),
Routed(IpAddr),
Unmapped,
}
pub(crate) fn map_ips_to_interfaces_with(
ip_set: IpSet,
interfaces: Vec<Link>,
forced: &[IpAddr],
) -> RoutedTargets {
let owned_ips: HashSet<IpAddr> = interfaces
.iter()
.flat_map(|link| link.addresses().iter().map(|held| held.address()))
.collect();
let mut local: HashMap<usize, IpSet> = HashMap::new();
let mut routed: Vec<RoutedTarget> = Vec::new();
let mut unmapped = IpSet::new();
let mut ours = IpSet::new();
let mut unenumerable: Vec<Ipv6Range> = Vec::new();
let mut ambiguous: Vec<Ipv6Range> = Vec::new();
let mut singles_to_route: Vec<IpAddr> = Vec::new();
for range in ip_set.v4() {
let start = IpAddr::V4(range.start_addr());
let end = IpAddr::V4(range.end_addr());
match owning_interface(&interfaces, start, end) {
Some(idx) => local.entry(idx).or_default().insert_range(V4(*range)),
None => singles_to_route.extend(range.iter()),
}
}
for range in ip_set.v6() {
let start = IpAddr::V6(range.start_addr());
let end = IpAddr::V6(range.end_addr());
if range.is_ambiguous() {
ambiguous.push(*range);
continue;
}
if let Some(zone) = range.zone() {
match interfaces.iter().position(|link| link.index() == zone) {
Some(idx) => local.entry(idx).or_default().insert_range(V6(*range)),
None => ambiguous.push(*range),
}
continue;
}
match owning_interface(&interfaces, start, end) {
Some(idx) => local.entry(idx).or_default().insert_range(V6(*range)),
None if !is_enumerable(range) => unenumerable.push(*range),
None => singles_to_route.extend(range.iter()),
}
}
let processed: Vec<(IpAddr, Classification)> = singles_to_route
.par_iter()
.map_init(ProbeSockets::default, |sockets, &target| {
if target.is_loopback() {
return (target, Classification::Unmapped);
}
if is_ipv4_mapped(target) {
return (target, Classification::Unmapped);
}
if let Some(idx) = find_local_index(&interfaces, target) {
return (target, Classification::Local(idx));
}
if let Some(source) = forced
.iter()
.copied()
.find(|s| s.is_ipv4() == target.is_ipv4())
{
return (target, Classification::Routed(source));
}
if let Some(source) = probe_route_source(target, sockets)
&& owned_ips.contains(&source)
{
return (target, Classification::Routed(source));
}
if let Some(source) = plausible_source(&interfaces, target) {
return (target, Classification::Routed(source));
}
(target, Classification::Unmapped)
})
.collect();
for (target, class) in processed {
match class {
Classification::Local(idx) => local.entry(idx).or_default().insert(target),
Classification::Routed(source) => routed.push(RoutedTarget { target, source }),
Classification::Unmapped => unmapped.insert(target),
}
}
for address in &owned_ips {
let mut one = IpSet::new();
one.insert(*address);
for targets in local.values_mut() {
if targets.contains(address) {
targets.subtract(&one);
ours.insert(*address);
}
}
if unmapped.contains(address) {
unmapped.subtract(&one);
ours.insert(*address);
}
}
local.retain(|_, targets| !targets.is_empty());
let local = local
.into_iter()
.map(|(idx, ips)| (interfaces[idx].clone(), ips))
.collect();
RoutedTargets {
local,
routed,
unmapped,
ours,
ambiguous,
unenumerable,
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum FrameSender {
Sweep,
Probe,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum Unframed {
Loopback,
Ours,
Tunnel(String),
NoRoute,
Neighbour(String),
Mapped,
}
impl std::fmt::Display for Unframed {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Loopback => f.write_str("loopback"),
Self::Ours => f.write_str("own address"),
Self::Tunnel(link) => write!(f, "via {link}"),
Self::NoRoute => f.write_str("no route"),
Self::Neighbour(link) => write!(f, "IPv6 neighbour on {link}, no NDP"),
Self::Mapped => f.write_str("IPv4-mapped"),
}
}
}
#[derive(Debug, Default)]
pub(crate) struct BeyondFrames {
pub(crate) targets: IpSet,
reasons: Vec<(Unframed, IpSet)>,
}
impl BeyondFrames {
pub(crate) fn is_empty(&self) -> bool {
self.targets.is_empty()
}
pub(crate) fn summary(&self) -> Vec<(Unframed, IpAddr, u128)> {
self.reasons
.iter()
.filter_map(|(reason, targets)| {
let first = targets.iter().next()?;
Some((reason.clone(), first, targets.len()))
})
.collect()
}
fn note(&mut self, reason: Unframed, mut targets: IpSet) {
targets.canonicalize();
if targets.is_empty() {
return;
}
extend(&mut self.targets, &targets);
self.reasons.push((reason, targets));
}
}
fn is_ipv4_mapped(target: IpAddr) -> bool {
matches!(target, IpAddr::V6(v6) if v6.to_ipv4_mapped().is_some())
}
fn extend(into: &mut IpSet, from: &IpSet) {
for range in from.v4() {
into.push_v4_range(*range);
}
for range in from.v6() {
into.push_v6_range(*range);
}
}
pub(crate) fn beyond_frames(ip_set: IpSet, forced: &[IpAddr], sender: FrameSender) -> BeyondFrames {
beyond_frames_with(ip_set, viable_interfaces(), forced, sender)
}
pub(crate) fn beyond_frames_with(
ip_set: IpSet,
interfaces: Vec<Link>,
forced: &[IpAddr],
sender: FrameSender,
) -> BeyondFrames {
let links = interfaces.clone();
let RoutedTargets {
local,
routed,
unmapped,
ours,
..
} = map_ips_to_interfaces_with(ip_set, interfaces, forced);
let mut groups: Vec<(Unframed, IpSet)> = Vec::new();
let mut add = |reason: Unframed, range: IpRange| match groups
.iter_mut()
.find(|(held, _)| *held == reason)
{
Some((_, targets)) => targets.insert_range(range),
None => {
let mut targets = IpSet::new();
targets.insert_range(range);
groups.push((reason, targets));
}
};
for address in unmapped.iter() {
let reason = if address.is_loopback() {
Unframed::Loopback
} else if is_ipv4_mapped(address) {
Unframed::Mapped
} else {
Unframed::NoRoute
};
add(reason, single(address));
}
for range in ours.v4() {
add(Unframed::Ours, V4(*range));
}
for range in ours.v6() {
add(Unframed::Ours, V6(*range));
}
let mut local: Vec<(Link, IpSet)> = local.into_iter().collect();
local.sort_by(|(a, _), (b, _)| a.name().cmp(b.name()));
for (link, targets) in &local {
if !link.carries_frames() {
for range in targets.v4() {
add(Unframed::Tunnel(link.name().to_string()), V4(*range));
}
for range in targets.v6() {
add(Unframed::Tunnel(link.name().to_string()), V6(*range));
}
} else if sender == FrameSender::Probe {
for range in targets.v6() {
add(Unframed::Neighbour(link.name().to_string()), V6(*range));
}
}
}
for RoutedTarget { target, source } in routed {
let Some(owner) = links
.iter()
.find(|link| link.addresses().iter().any(|held| held.address() == source))
else {
continue;
};
if !owner.carries_frames() {
add(Unframed::Tunnel(owner.name().to_string()), single(target));
}
}
let mut beyond = BeyondFrames::default();
for (reason, targets) in groups {
beyond.note(reason, targets);
}
beyond.targets.canonicalize();
beyond
}
fn single(address: IpAddr) -> IpRange {
match address {
IpAddr::V4(v4) => V4(Ipv4Range::single(v4)),
IpAddr::V6(v6) => V6(Ipv6Range::single(v6)),
}
}
pub fn is_enumerable(range: &Ipv6Range) -> bool {
range.len() <= MAX_ENUMERABLE_ADDRESSES
}
fn owning_interface(links: &[Link], start: IpAddr, end: IpAddr) -> Option<usize> {
links.iter().position(|link| {
link.addresses()
.iter()
.any(|held| held.contains(&start) && held.contains(&end))
})
}
fn find_local_index(links: &[Link], target: IpAddr) -> Option<usize> {
links
.iter()
.position(|link| link.addresses().iter().any(|held| held.contains(&target)))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::model::ip::range::{IpRange, Ipv4Range, Ipv6Range};
use std::net::{Ipv4Addr, Ipv6Addr};
fn mock_named(name: &str, index: u32, ip: IpAddr, prefix: u8) -> Link {
Link::new(name, index)
.with_addresses(vec![crate::system::interface::LinkAddress::new(ip, prefix)])
}
fn mock_interface(ip: IpAddr, prefix: u8) -> Link {
Link::new("test0", 0)
.with_addresses(vec![crate::system::interface::LinkAddress::new(ip, prefix)])
}
#[test]
fn test_find_local_index() {
let interfaces = vec![
mock_interface(IpAddr::V4(Ipv4Addr::new(192, 0, 2, 100)), 24),
mock_interface(IpAddr::V4(Ipv4Addr::new(198, 51, 100, 5)), 24),
];
assert_eq!(
find_local_index(&interfaces, IpAddr::V4(Ipv4Addr::new(192, 0, 2, 50))),
Some(0)
);
assert_eq!(
find_local_index(&interfaces, IpAddr::V4(Ipv4Addr::new(198, 51, 100, 200))),
Some(1)
);
assert_eq!(
find_local_index(&interfaces, IpAddr::V4(Ipv4Addr::new(203, 0, 113, 1))),
None
);
}
#[test]
fn on_link_v4_range_stays_intact_and_local() {
let interfaces = vec![mock_interface(IpAddr::V4(Ipv4Addr::new(192, 0, 2, 1)), 24)];
let mut set = IpSet::new();
set.insert_range(IpRange::V4(
Ipv4Range::new(Ipv4Addr::new(192, 0, 2, 10), Ipv4Addr::new(192, 0, 2, 20)).unwrap(),
));
let result = map_ips_to_interfaces_with(set, interfaces, &[]);
assert!(result.routed.is_empty());
assert!(result.unmapped.is_empty());
assert_eq!(result.local.len(), 1);
let (_, ips) = result.local.into_iter().next().unwrap();
assert_eq!(ips.len(), 11);
}
#[test]
fn the_enumeration_ceiling_is_a_112() {
let base = Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, 0);
let at_ceiling = Ipv6Range::new(base, Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, 0xffff));
let over_ceiling = Ipv6Range::new(base, Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 1, 0));
let at_ceiling = at_ceiling.unwrap();
assert_eq!(at_ceiling.len(), MAX_ENUMERABLE_ADDRESSES);
assert!(is_enumerable(&at_ceiling), "a /112 is 65536 addresses");
assert!(
!is_enumerable(&over_ceiling.unwrap()),
"one address more is not"
);
}
#[test]
fn a_routed_v6_prefix_too_large_to_walk_is_refused_rather_than_expanded() {
let interfaces = vec![mock_interface(IpAddr::V4(Ipv4Addr::new(192, 0, 2, 1)), 24)];
let mut set = IpSet::new();
set.insert_range(IpRange::V6(
Ipv6Range::new(
Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, 0),
Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0xffff, 0xffff, 0xffff, 0xffff),
)
.unwrap(),
));
let result = map_ips_to_interfaces_with(set, interfaces, &[]);
assert_eq!(result.unenumerable.len(), 1, "the /64 is reported whole");
assert!(result.routed.is_empty());
assert!(result.unmapped.is_empty());
assert!(result.local.is_empty());
}
#[test]
fn a_link_local_target_naming_no_interface_is_refused() {
let link_local = Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 0xAA);
let interfaces = vec![
mock_interface(IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 1)), 64),
mock_interface(IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 2)), 64),
];
let mut set = IpSet::new();
set.insert(IpAddr::V6(link_local));
let result = map_ips_to_interfaces_with(set, interfaces, &[]);
assert_eq!(result.ambiguous.len(), 1);
assert!(
result.local.is_empty(),
"guessing an interface is what this prevents"
);
}
#[test]
fn a_link_local_target_goes_to_the_interface_it_names() {
let link_local = Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 0xAA);
let first = mock_named(
"en3",
3,
IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 1)),
64,
);
let second = mock_named(
"en9",
9,
IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 2)),
64,
);
let mut set = IpSet::new();
set.insert_range(IpRange::V6(
Ipv6Range::scoped(link_local, link_local, Some(9)).unwrap(),
));
let result = map_ips_to_interfaces_with(set, vec![first, second], &[]);
assert!(result.ambiguous.is_empty());
assert_eq!(result.local.len(), 1);
let (intf, ips) = result.local.into_iter().next().unwrap();
assert_eq!(intf.name(), "en9", "the second interface was the one named");
assert_eq!(ips.len(), 1);
}
#[test]
fn on_link_v6_range_is_classified_local() {
let base = Ipv6Addr::new(0xfd00, 0, 0, 0, 0, 0, 0, 0);
let interfaces = vec![mock_interface(IpAddr::V6(base), 64)];
let mut set = IpSet::new();
set.insert_range(IpRange::V6(
Ipv6Range::new(
Ipv6Addr::new(0xfd00, 0, 0, 0, 0, 0, 0, 1),
Ipv6Addr::new(0xfd00, 0, 0, 0, 0, 0, 0, 5),
)
.unwrap(),
));
let result = map_ips_to_interfaces_with(set, interfaces, &[]);
assert!(result.routed.is_empty());
assert!(result.unmapped.is_empty());
assert_eq!(result.local.len(), 1);
let (_, ips) = result.local.into_iter().next().unwrap();
assert_eq!(ips.len(), 5);
}
#[test]
fn an_address_this_host_holds_is_ours_rather_than_on_link() {
let own: IpAddr = "203.0.113.160".parse().unwrap();
let interfaces = vec![mock_interface(own, 24)];
let mut targets = IpSet::new();
targets.insert(own);
let routed = map_ips_to_interfaces_with(targets, interfaces, &[]);
assert!(routed.ours.contains(&own), "the address is this host's own");
assert!(
routed.local.is_empty(),
"and must not be handed to a link-layer strategy"
);
}
#[test]
fn a_neighbour_on_the_same_segment_is_still_on_link() {
let own: IpAddr = "203.0.113.160".parse().unwrap();
let neighbour: IpAddr = "203.0.113.101".parse().unwrap();
let interfaces = vec![mock_interface(own, 24)];
let mut targets = IpSet::new();
targets.insert(neighbour);
let routed = map_ips_to_interfaces_with(targets, interfaces, &[]);
assert!(routed.ours.is_empty());
assert_eq!(
routed.local.values().next().map(IpSet::len),
Some(1u128),
"the neighbour is on-link"
);
}
fn ethernet(addresses: &[(&str, u8)]) -> Link {
Link::new("en0", 4)
.with_mac(crate::model::mac::MacAddr::new(0x02, 0, 0, 0, 0, 0x10))
.with_kind(crate::system::interface::LinkKind::Wired)
.with_addressing(crate::system::interface::Addressing::Broadcast)
.with_link_up(true)
.with_addresses(held(addresses))
}
fn tunnel(addresses: &[(&str, u8)]) -> Link {
Link::new("utun9", 20)
.with_addressing(crate::system::interface::Addressing::PointToPoint)
.with_link_up(true)
.with_addresses(held(addresses))
}
fn held(addresses: &[(&str, u8)]) -> Vec<crate::system::interface::LinkAddress> {
addresses
.iter()
.map(|(address, prefix)| {
crate::system::interface::LinkAddress::new(
address.parse().expect("a literal"),
*prefix,
)
})
.collect()
}
fn set_of(addresses: &[&str]) -> IpSet {
let mut set = IpSet::new();
for address in addresses {
set.insert(address.parse().expect("a literal"));
}
set
}
fn ip(literal: &str) -> IpAddr {
literal.parse().expect("a literal")
}
#[test]
fn loopback_is_unmapped_in_both_families_whatever_is_forced() {
let interfaces = vec![ethernet(&[("192.0.2.10", 24), ("2001:db8:1::10", 64)])];
let forced = [ip("192.0.2.10"), ip("2001:db8:1::10")];
for forced in [&forced[..], &[]] {
let routed = map_ips_to_interfaces_with(
set_of(&["127.0.0.1", "::1"]),
interfaces.clone(),
forced,
);
assert!(
routed.routed.is_empty(),
"loopback is not behind a gateway: {:?}",
routed.routed
);
assert!(routed.unmapped.contains(&ip("127.0.0.1")));
assert!(routed.unmapped.contains(&ip("::1")));
}
}
#[test]
fn a_mapped_address_is_unmapped_whatever_is_forced() {
let interfaces = vec![ethernet(&[("192.0.2.10", 24), ("2001:db8:1::10", 64)])];
let forced = [ip("192.0.2.10"), ip("2001:db8:1::10")];
for forced in [&forced[..], &[]] {
let routed = map_ips_to_interfaces_with(
set_of(&["::ffff:127.0.0.1", "::ffff:198.51.100.7"]),
interfaces.clone(),
forced,
);
assert!(
routed.routed.is_empty(),
"a mapped address is not behind a gateway: {:?}",
routed.routed
);
assert!(routed.unmapped.contains(&ip("::ffff:127.0.0.1")));
assert!(routed.unmapped.contains(&ip("::ffff:198.51.100.7")));
}
}
#[test]
fn a_mapped_address_is_beyond_frames_as_what_it_is() {
let beyond = beyond_frames_with(
set_of(&["::ffff:198.51.100.7"]),
vec![ethernet(&[("192.0.2.10", 24), ("2001:db8:1::10", 64)])],
&[],
FrameSender::Probe,
);
assert_eq!(
beyond.summary(),
vec![(Unframed::Mapped, ip("::ffff:198.51.100.7"), 1)]
);
}
#[test]
fn a_frame_reaches_an_ipv4_neighbour_and_a_target_routed_over_ethernet() {
let beyond = beyond_frames_with(
set_of(&["192.0.2.50", "203.0.113.9"]),
vec![ethernet(&[("192.0.2.10", 24)])],
&[ip("192.0.2.10")],
FrameSender::Probe,
);
assert!(beyond.is_empty(), "nothing out of reach: {beyond:?}");
}
#[test]
fn a_target_routed_through_a_tunnel_is_beyond_frames() {
let beyond = beyond_frames_with(
set_of(&["203.0.113.23"]),
vec![
ethernet(&[("192.0.2.10", 24)]),
tunnel(&[("198.51.100.2", 32)]),
],
&[ip("198.51.100.2")],
FrameSender::Sweep,
);
assert!(beyond.targets.contains(&ip("203.0.113.23")));
assert_eq!(
beyond.summary(),
vec![(Unframed::Tunnel("utun9".into()), ip("203.0.113.23"), 1)]
);
}
#[test]
fn a_tunnels_own_subnet_is_beyond_frames_under_the_same_reason() {
let beyond = beyond_frames_with(
set_of(&["198.51.100.7", "203.0.113.23"]),
vec![tunnel(&[("198.51.100.2", 24)])],
&[ip("198.51.100.2")],
FrameSender::Sweep,
);
assert_eq!(beyond.targets.len(), 2);
assert_eq!(
beyond.summary(),
vec![(Unframed::Tunnel("utun9".into()), ip("198.51.100.7"), 2)]
);
}
#[test]
fn an_ipv6_neighbour_is_within_the_sweep_and_beyond_the_probe_sender() {
let interfaces = vec![ethernet(&[("192.0.2.10", 24), ("2001:db8:1::10", 64)])];
let targets = set_of(&["2001:db8:1::20", "192.0.2.50"]);
let swept =
beyond_frames_with(targets.clone(), interfaces.clone(), &[], FrameSender::Sweep);
assert!(swept.is_empty(), "the sweep reaches both: {swept:?}");
let probed = beyond_frames_with(targets, interfaces, &[], FrameSender::Probe);
assert_eq!(
probed.summary(),
vec![(Unframed::Neighbour("en0".into()), ip("2001:db8:1::20"), 1)],
"and the probe sender only the IPv4 one"
);
}
#[test]
fn loopback_and_this_hosts_own_addresses_are_beyond_frames() {
let beyond = beyond_frames_with(
set_of(&["127.0.0.1", "::1", "192.0.2.10"]),
vec![ethernet(&[("192.0.2.10", 24)])],
&[],
FrameSender::Probe,
);
assert_eq!(
beyond.summary(),
vec![
(Unframed::Loopback, ip("127.0.0.1"), 2),
(Unframed::Ours, ip("192.0.2.10"), 1),
]
);
}
#[test]
fn a_forced_source_outranks_the_routing_table_for_a_routed_target() {
let lan: IpAddr = "203.0.113.160".parse().unwrap();
let public: IpAddr = "1.1.1.1".parse().unwrap();
let interfaces = vec![mock_interface(lan, 24)];
let mut targets = IpSet::new();
targets.insert(public);
let routed = map_ips_to_interfaces_with(targets, interfaces, &[lan]);
assert_eq!(
routed.routed,
vec![RoutedTarget {
target: public,
source: lan
}],
"the off-link target is probed from the forced source"
);
}
}