use std::collections::hash_map::Entry;
use std::collections::{HashMap, HashSet};
use std::net::IpAddr;
use std::sync::Arc;
use crate::model::host::Host;
use crate::model::mac::MacAddr;
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
pub enum HostIdentity {
PrimaryAddress,
#[default]
AnyAddress,
Hardware,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct Component {
pub(crate) baseline: Vec<usize>,
pub(crate) current: Vec<usize>,
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum Token {
Address(IpAddr, Option<Arc<str>>),
Hardware(MacAddr),
}
pub(crate) fn components(
baseline: &[&Host],
current: &[&Host],
identity: HostIdentity,
) -> Vec<Component> {
let baseline_tokens: Vec<HashSet<Token>> =
baseline.iter().map(|host| tokens(host, identity)).collect();
let current_tokens: Vec<HashSet<Token>> =
current.iter().map(|host| tokens(host, identity)).collect();
let mut baseline_index = index(&baseline_tokens);
let mut current_index = index(¤t_tokens);
let mut baseline_seen = vec![false; baseline.len()];
let mut current_seen = vec![false; current.len()];
let mut components = Vec::new();
for start in 0..baseline.len() {
if baseline_seen[start] {
continue;
}
baseline_seen[start] = true;
let mut component = Component {
baseline: Vec::new(),
current: Vec::new(),
};
let mut baseline_queue = vec![start];
let mut current_queue: Vec<usize> = Vec::new();
while !baseline_queue.is_empty() || !current_queue.is_empty() {
while let Some(i) = baseline_queue.pop() {
component.baseline.push(i);
for token in &baseline_tokens[i] {
for j in current_index.remove(token).unwrap_or_default() {
if !current_seen[j] {
current_seen[j] = true;
current_queue.push(j);
}
}
}
}
while let Some(j) = current_queue.pop() {
component.current.push(j);
for token in ¤t_tokens[j] {
for i in baseline_index.remove(token).unwrap_or_default() {
if !baseline_seen[i] {
baseline_seen[i] = true;
baseline_queue.push(i);
}
}
}
}
}
component.baseline.sort_unstable();
component.current.sort_unstable();
components.push(component);
}
for (j, seen) in current_seen.iter().enumerate() {
if !seen {
components.push(Component {
baseline: Vec::new(),
current: vec![j],
});
}
}
components.sort_by_key(|component| {
(
component.baseline.first().copied().unwrap_or(usize::MAX),
component.current.first().copied().unwrap_or(usize::MAX),
)
});
components
}
pub(crate) fn groups(records: &[&Host], identity: HostIdentity) -> Vec<Vec<usize>> {
let mut sets = DisjointSet::new(records.len());
let mut first_holder: HashMap<Token, usize> = HashMap::new();
for (i, host) in records.iter().enumerate() {
for token in tokens(host, identity) {
match first_holder.entry(token) {
Entry::Occupied(held) => sets.union(*held.get(), i),
Entry::Vacant(slot) => {
slot.insert(i);
}
}
}
}
let mut grouped: HashMap<usize, Vec<usize>> = HashMap::new();
let mut order: Vec<usize> = Vec::new();
for i in 0..records.len() {
let root = sets.find(i);
grouped.entry(root).or_insert_with(|| {
order.push(root);
Vec::new()
});
grouped.get_mut(&root).expect("just inserted").push(i);
}
order
.into_iter()
.map(|root| grouped.remove(&root).expect("a root that was recorded"))
.collect()
}
struct DisjointSet {
parent: Vec<usize>,
size: Vec<usize>,
}
impl DisjointSet {
fn new(len: usize) -> Self {
Self {
parent: (0..len).collect(),
size: vec![1; len],
}
}
fn find(&mut self, mut i: usize) -> usize {
while self.parent[i] != i {
self.parent[i] = self.parent[self.parent[i]];
i = self.parent[i];
}
i
}
fn union(&mut self, a: usize, b: usize) {
let (mut a, mut b) = (self.find(a), self.find(b));
if a == b {
return;
}
if self.size[a] < self.size[b] {
std::mem::swap(&mut a, &mut b);
}
self.parent[b] = a;
self.size[a] += self.size[b];
}
}
fn tokens(host: &Host, identity: HostIdentity) -> HashSet<Token> {
let zone = host.zone().map(|zone| Arc::from(zone.name()));
let mut tokens: HashSet<Token> = match identity {
HostIdentity::PrimaryAddress => {
let ip = host.primary_ip();
HashSet::from([Token::Address(ip, scope_of(&ip, &zone))])
}
HostIdentity::AnyAddress | HostIdentity::Hardware => host
.ips()
.iter()
.map(|ip| Token::Address(*ip, scope_of(ip, &zone)))
.collect(),
};
if identity == HostIdentity::Hardware
&& let Some(hardware) = host.hardware()
{
tokens.extend(hardware.macs().keys().copied().map(Token::Hardware));
}
tokens
}
fn scope_of(ip: &IpAddr, zone: &Option<Arc<str>>) -> Option<Arc<str>> {
is_link_local(ip).then(|| zone.clone()).flatten()
}
fn is_link_local(ip: &IpAddr) -> bool {
match ip {
IpAddr::V4(v4) => v4.is_link_local(),
IpAddr::V6(v6) => (v6.segments()[0] & 0xffc0) == 0xfe80,
}
}
fn index(tokens: &[HashSet<Token>]) -> HashMap<&Token, Vec<usize>> {
let mut index: HashMap<&Token, Vec<usize>> = HashMap::new();
for (i, set) in tokens.iter().enumerate() {
for token in set {
index.entry(token).or_default().push(i);
}
}
index
}
#[cfg(test)]
mod tests {
use std::net::{Ipv4Addr, Ipv6Addr};
use super::*;
use crate::model::host::HostStatus;
use crate::model::ip::scoped::Zone;
use crate::model::mac::MacAddr;
fn v4(last: u8) -> IpAddr {
IpAddr::V4(Ipv4Addr::new(192, 168, 0, last))
}
fn host(primary: IpAddr) -> Host {
let mut host = Host::new(primary);
host.set_status(HostStatus::Up);
host
}
fn shape(components: &[Component]) -> Vec<(Vec<usize>, Vec<usize>)> {
let mut out: Vec<(Vec<usize>, Vec<usize>)> = components
.iter()
.map(|c| {
let mut b = c.baseline.clone();
let mut n = c.current.clone();
b.sort_unstable();
n.sort_unstable();
(b, n)
})
.collect();
out.sort();
out
}
#[test]
fn a_host_at_the_same_address_pairs_with_itself() {
let before = [host(v4(1))];
let after = [host(v4(1))];
let components = components(
&before.iter().collect::<Vec<_>>(),
&after.iter().collect::<Vec<_>>(),
HostIdentity::AnyAddress,
);
assert_eq!(shape(&components), vec![(vec![0], vec![0])]);
}
#[test]
fn hosts_sharing_no_address_do_not_pair() {
let before = [host(v4(1))];
let after = [host(v4(2))];
let components = components(
&before.iter().collect::<Vec<_>>(),
&after.iter().collect::<Vec<_>>(),
HostIdentity::AnyAddress,
);
assert_eq!(
shape(&components),
vec![(vec![], vec![0]), (vec![0], vec![])],
"one host went away and another arrived"
);
}
#[test]
fn a_shared_secondary_address_pairs_two_records() {
let mut before = host(v4(1));
before.add_ip(v4(50));
let after = host(v4(50));
let components = components(&[&before], &[&after], HostIdentity::AnyAddress);
assert_eq!(shape(&components), vec![(vec![0], vec![0])]);
}
#[test]
fn a_shared_secondary_address_does_not_pair_under_primary_address() {
let mut before = host(v4(1));
before.add_ip(v4(50));
let after = host(v4(50));
let components = components(&[&before], &[&after], HostIdentity::PrimaryAddress);
assert_eq!(
shape(&components),
vec![(vec![], vec![0]), (vec![0], vec![])]
);
}
#[test]
fn records_the_two_scans_grouped_differently_form_one_component() {
let mut merged = host(v4(1));
merged.add_ip(v4(2));
let split_a = host(v4(1));
let split_b = host(v4(2));
let components = components(&[&merged], &[&split_a, &split_b], HostIdentity::AnyAddress);
assert_eq!(shape(&components), vec![(vec![0], vec![0, 1])]);
}
#[test]
fn link_local_addresses_on_different_zones_are_different_hosts() {
let link_local = IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 1));
let mut before = Host::new(link_local);
before.set_zone(Zone::new(1, "en0"));
before.set_status(HostStatus::Up);
let mut after = Host::new(link_local);
after.set_zone(Zone::new(2, "en1"));
after.set_status(HostStatus::Up);
let components = components(&[&before], &[&after], HostIdentity::AnyAddress);
assert_eq!(
shape(&components),
vec![(vec![], vec![0]), (vec![0], vec![])],
"the same link-local address on two segments is two machines"
);
}
#[test]
fn hardware_identity_pairs_a_host_that_changed_address() {
let mac = MacAddr::new(0x2c, 0xcf, 0x67, 0xf2, 0x51, 0xe3);
let mut before = host(v4(1));
before.record_mac(mac);
let mut after = host(v4(2));
after.record_mac(mac);
let components = components(&[&before], &[&after], HostIdentity::Hardware);
assert_eq!(
shape(&components),
vec![(vec![0], vec![0])],
"a DHCP lease moving is not a host being replaced"
);
}
#[test]
fn groups_folds_records_that_share_an_address() {
let mut one = host(v4(1));
one.add_ip(v4(9));
let two = host(v4(9));
let three = host(v4(3));
let mut groups = groups(&[&one, &two, &three], HostIdentity::AnyAddress);
for group in &mut groups {
group.sort_unstable();
}
groups.sort();
assert_eq!(groups, vec![vec![0, 1], vec![2]]);
}
}