use crate::model::ip::range::IpRange::{V4, V6};
use crate::model::ip::range::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 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,
}
}
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, 168, 1, 100)), 24),
mock_interface(IpAddr::V4(Ipv4Addr::new(10, 0, 0, 5)), 8),
];
assert_eq!(
find_local_index(&interfaces, IpAddr::V4(Ipv4Addr::new(192, 168, 1, 50))),
Some(0)
);
assert_eq!(
find_local_index(&interfaces, IpAddr::V4(Ipv4Addr::new(10, 50, 0, 1))),
Some(1)
);
assert_eq!(
find_local_index(&interfaces, IpAddr::V4(Ipv4Addr::new(172, 16, 0, 1))),
None
);
}
#[test]
fn on_link_v4_range_stays_intact_and_local() {
let interfaces = vec![mock_interface(
IpAddr::V4(Ipv4Addr::new(192, 168, 1, 1)),
24,
)];
let mut set = IpSet::new();
set.insert_range(IpRange::V4(
Ipv4Range::new(
Ipv4Addr::new(192, 168, 1, 10),
Ipv4Addr::new(192, 168, 1, 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, 168, 1, 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 = "192.168.0.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 = "192.168.0.160".parse().unwrap();
let neighbour: IpAddr = "192.168.0.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"
);
}
#[test]
fn a_forced_source_outranks_the_routing_table_for_a_routed_target() {
let lan: IpAddr = "192.168.0.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"
);
}
}