use std::collections::{BTreeMap, HashMap};
use std::net::IpAddr;
use std::time::{Duration, Instant};
use crate::scanner::session::ScanContext;
use crate::system::interface::SourceResolver;
use crate::transport::kernel_neighbors::{KernelNeighbors, NeighborState};
use crate::transport::link::ARP_TIMEOUT;
use crate::transport::probe::NeighborWatch;
pub(crate) const NEIGHBOR_RECHECK: Duration = Duration::from_millis(50);
pub(crate) const RESOLUTION_BUDGET: Duration = ARP_TIMEOUT.saturating_add(NEIGHBOR_RECHECK);
pub(crate) const NEIGHBOR_ROUNDS: u8 = 2;
pub(crate) const NEIGHBOR_BUDGET: Duration =
RESOLUTION_BUDGET.saturating_mul(NEIGHBOR_ROUNDS as u32);
pub(crate) const RESOLUTION_WAIT_LIMIT: Duration = RESOLUTION_BUDGET.saturating_mul(2);
pub(crate) const HELD_DOWN_REFUSALS: u8 = 2;
#[derive(Debug)]
pub(crate) struct HoldDowns {
held: HashMap<IpAddr, HeldDown>,
pub(crate) hold_down_for: Duration,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct HeldDown {
refusals: u8,
until: Instant,
}
impl Default for HoldDowns {
fn default() -> Self {
Self {
held: HashMap::new(),
hold_down_for: crate::transport::kernel_neighbors::hold_down(),
}
}
}
impl HoldDowns {
pub(crate) fn hold(&mut self, host: IpAddr, now: Instant) -> Option<Instant> {
let held = self.held.entry(host).or_insert(HeldDown {
refusals: 0,
until: now,
});
if held.until > now {
return Some(held.until);
}
held.refusals = held.refusals.saturating_add(1);
if held.refusals >= HELD_DOWN_REFUSALS {
return None;
}
held.until = crate::scanner::pacing::timer::later(now, self.hold_down_for);
Some(held.until)
}
pub(crate) fn until(&self, host: IpAddr, now: Instant) -> Option<Instant> {
self.held
.get(&host)
.map(|held| held.until)
.filter(|until| *until > now)
}
#[cfg(all(test, unix))]
pub(crate) fn lift(&mut self, host: IpAddr) {
if let Some(held) = self.held.get_mut(&host) {
held.until = Instant::now();
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum NeighborGate {
Asked {
at: Instant,
round: u8,
},
Open,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Admission {
Send,
Hold(Instant),
Unreachable,
}
#[derive(Debug, Default)]
pub(crate) struct NeighborGates {
gates: HashMap<IpAddr, NeighborGate>,
gated: HashMap<IpAddr, IpAddr>,
given_up: HashMap<IpAddr, NeighborState>,
asked_again: Option<Instant>,
}
impl NeighborGates {
pub(crate) fn admit(
&mut self,
watch: Option<&NeighborWatch>,
resolver: &mut SourceResolver,
host: IpAddr,
now: Instant,
) -> Admission {
let Some(watch) = watch else {
return Admission::Send;
};
let Some(neighbor) = neighbor_of(watch, resolver, host) else {
return Admission::Send;
};
let (asked, round) = match self.gates.get(&neighbor) {
Some(NeighborGate::Open) => return Admission::Send,
Some(NeighborGate::Asked { at, round }) => (*at, *round),
None if matches!(watch, NeighborWatch::Kernel(_)) => {
self.ask(neighbor, 1);
self.gated.insert(host, neighbor);
return Admission::Send;
}
None => (self.ask(neighbor, 1), 1),
};
self.gated.insert(host, neighbor);
match state(watch, resolver, host, neighbor, asked) {
Some(NeighborState::Resolving)
if now.saturating_duration_since(asked) >= RESOLUTION_WAIT_LIMIT =>
{
self.given_up.insert(neighbor, NeighborState::Resolving);
Admission::Unreachable
}
Some(NeighborState::Resolving) => Admission::Hold(now + NEIGHBOR_RECHECK),
Some(NeighborState::Failed) if round < NEIGHBOR_ROUNDS => {
self.asked_again = Some(self.ask(neighbor, round + 1));
match watch {
NeighborWatch::Kernel(_) => Admission::Send,
NeighborWatch::Frames(link) => {
if let Some(source) = resolver.resolve(host) {
link.ask_again(source, host);
}
Admission::Hold(now + NEIGHBOR_RECHECK)
}
}
}
Some(NeighborState::Failed) => {
self.given_up.insert(neighbor, NeighborState::Failed);
Admission::Unreachable
}
Some(NeighborState::Resolved) | None => {
self.gates.insert(neighbor, NeighborGate::Open);
Admission::Send
}
}
}
fn ask(&mut self, neighbor: IpAddr, round: u8) -> Instant {
let at = Instant::now();
self.gates
.insert(neighbor, NeighborGate::Asked { at, round });
at
}
pub(crate) fn take_asked_again(&mut self) -> Option<Instant> {
self.asked_again.take()
}
fn open_held(
&mut self,
watch: &NeighborWatch,
table: &KernelNeighbors,
resolver: &SourceResolver,
hosts: &[IpAddr],
) {
let read = Instant::now();
for host in hosts {
let Some(neighbor) = neighbor_of(watch, resolver, *host) else {
continue;
};
if table.state(neighbor, read) == Some(NeighborState::Resolved) {
self.gates.insert(neighbor, NeighborGate::Open);
}
}
}
pub(crate) fn pending(
&self,
watch: Option<&NeighborWatch>,
resolver: &mut SourceResolver,
host: IpAddr,
) -> Option<NeighborState> {
let neighbor = *self.gated.get(&host)?;
let Some(NeighborGate::Asked { at, .. }) = self.gates.get(&neighbor).copied() else {
return None;
};
state(watch?, resolver, host, neighbor, at)
}
pub(crate) fn waiting(&self) -> Vec<IpAddr> {
self.gated
.keys()
.copied()
.filter(|host| self.is_waiting(*host))
.collect()
}
pub(crate) fn is_waiting(&self, host: IpAddr) -> bool {
self.gated.get(&host).is_some_and(|neighbor| {
matches!(self.gates.get(neighbor), Some(NeighborGate::Asked { .. }))
})
}
pub(crate) fn refusal(&self, host: IpAddr) -> String {
self.unreached(host, self.given_up_in(host))
}
pub(crate) fn given_up_in(&self, host: IpAddr) -> NeighborState {
self.gated
.get(&host)
.and_then(|neighbor| self.given_up.get(neighbor))
.copied()
.unwrap_or(NeighborState::Failed)
}
pub(crate) fn unreached(&self, host: IpAddr, state: NeighborState) -> String {
unreached(host, self.gated.get(&host).copied(), state)
}
}
pub(crate) fn unreached(host: IpAddr, neighbor: Option<IpAddr>, state: NeighborState) -> String {
let resolution = if host.is_ipv4() { "ARP" } else { "NDP" };
let how = match state {
NeighborState::Failed => format!("no {resolution} reply"),
_ => format!("{resolution} pending"),
};
match neighbor.filter(|neighbor| *neighbor != host) {
Some(gateway) => format!("{how} from gateway {gateway}"),
None => how,
}
}
pub(crate) async fn resolve_ahead(
ctx: &ScanContext,
watch: Option<&NeighborWatch>,
resolver: &mut SourceResolver,
hosts: impl IntoIterator<Item = IpAddr>,
) -> (NeighborGates, BTreeMap<IpAddr, String>) {
let mut gates = NeighborGates::default();
let mut unanswered = BTreeMap::new();
let mut waiting: Vec<IpAddr> = hosts.into_iter().collect();
if let Some(watch @ NeighborWatch::Kernel(table)) = watch {
gates.open_held(watch, table, resolver, &waiting);
return (gates, unanswered);
}
while !waiting.is_empty() && !ctx.handle.should_stop() {
let now = Instant::now();
waiting.retain(|host| match gates.admit(watch, resolver, *host, now) {
Admission::Send => false,
Admission::Hold(_) => true,
Admission::Unreachable => {
unanswered.insert(*host, gates.refusal(*host));
false
}
});
if !waiting.is_empty() {
tokio::time::sleep(NEIGHBOR_RECHECK).await;
}
}
(gates, unanswered)
}
pub(crate) async fn admit_waiting(
gates: &mut NeighborGates,
ctx: &ScanContext,
watch: Option<&NeighborWatch>,
resolver: &mut SourceResolver,
host: IpAddr,
) -> Result<(), Option<String>> {
loop {
match gates.admit(watch, resolver, host, Instant::now()) {
Admission::Send => return Ok(()),
Admission::Unreachable => {
return Err(Some(gates.refusal(host)));
}
Admission::Hold(ready) => {
if ctx.handle.should_stop() {
return Err(None);
}
tokio::time::sleep_until(ready.into()).await;
}
}
}
}
pub(crate) async fn send_when_admitted<P>(
gates: &mut NeighborGates,
ctx: &ScanContext,
watch: Option<&NeighborWatch>,
resolver: &mut SourceResolver,
probes: Vec<(IpAddr, P)>,
mut send: impl FnMut(IpAddr, P),
) -> BTreeMap<IpAddr, String> {
let mut unreached = BTreeMap::new();
let mut held = probes;
loop {
let now = Instant::now();
let mut still = Vec::new();
for (host, probe) in held {
if unreached.contains_key(&host) {
continue;
}
if ctx.handle.should_stop() {
return unreached;
}
match gates.admit(watch, resolver, host, now) {
Admission::Send => send(host, probe),
Admission::Hold(_) => still.push((host, probe)),
Admission::Unreachable => {
unreached.insert(host, gates.refusal(host));
}
}
}
held = still;
if held.is_empty() || ctx.handle.should_stop() {
return unreached;
}
tokio::time::sleep(NEIGHBOR_RECHECK).await;
}
}
fn neighbor_of(watch: &NeighborWatch, resolver: &SourceResolver, host: IpAddr) -> Option<IpAddr> {
match watch {
NeighborWatch::Kernel(_) if resolver.is_on_link(host) => Some(host),
NeighborWatch::Kernel(table) => table.next_hop(host),
NeighborWatch::Frames(_) => Some(host),
}
}
fn state(
watch: &NeighborWatch,
resolver: &mut SourceResolver,
host: IpAddr,
neighbor: IpAddr,
asked: Instant,
) -> Option<NeighborState> {
match watch {
NeighborWatch::Kernel(table) => {
let recent = Instant::now()
.checked_sub(NEIGHBOR_RECHECK)
.map_or(asked, |recent| recent.max(asked));
table.state(neighbor, recent)
}
NeighborWatch::Frames(link) => {
let source = resolver.resolve(host)?;
link.state(source, host)
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::system::interface::{Link, LinkAddress};
use crate::transport::kernel_neighbors::{KernelNeighbors, NeighborTable};
use std::net::Ipv4Addr;
const HOST: IpAddr = IpAddr::V4(Ipv4Addr::new(192, 0, 2, 7));
fn kernel_showing(state: NeighborState) -> (NeighborWatch, SourceResolver) {
let table = KernelNeighbors::with_reader(Box::new(move || {
Ok(NeighborTable::from([(HOST, state)]))
}));
let resolver = SourceResolver::from_links(&[Link::new("test0", 1).with_addresses(vec![
LinkAddress::new(IpAddr::V4(Ipv4Addr::new(192, 0, 2, 1)), 24),
])]);
(NeighborWatch::Kernel(table), resolver)
}
#[test]
fn a_neighbour_that_never_concludes_is_given_up_on_at_the_limit() {
let (watch, mut resolver) = kernel_showing(NeighborState::Resolving);
let mut gates = NeighborGates::default();
let start = Instant::now();
assert_eq!(
gates.admit(Some(&watch), &mut resolver, HOST, start),
Admission::Send,
"the first write is what starts the kernel's asking"
);
let asked = Instant::now();
assert!(
matches!(
gates.admit(Some(&watch), &mut resolver, HOST, start),
Admission::Hold(_)
),
"and the probes behind it wait while it runs"
);
assert!(
matches!(
gates.admit(Some(&watch), &mut resolver, HOST, asked + RESOLUTION_BUDGET),
Admission::Hold(_)
),
"a resolution's own budget is not yet cause to give up"
);
assert_eq!(
gates.admit(
Some(&watch),
&mut resolver,
HOST,
asked + RESOLUTION_WAIT_LIMIT
),
Admission::Unreachable,
"a wait past any resolution's is an address nothing reaches"
);
}
#[test]
fn a_neighbour_given_up_at_the_limit_is_filed_pending_and_a_failed_one_not() {
let (watch, mut resolver) = kernel_showing(NeighborState::Resolving);
let mut gates = NeighborGates::default();
let start = Instant::now();
gates.admit(Some(&watch), &mut resolver, HOST, start);
let limit = Instant::now() + RESOLUTION_WAIT_LIMIT;
assert_eq!(
gates.admit(Some(&watch), &mut resolver, HOST, limit),
Admission::Unreachable
);
assert_eq!(gates.refusal(HOST), "ARP pending");
let (watch, mut resolver) = kernel_showing(NeighborState::Failed);
let mut gates = NeighborGates::default();
gates.admit(Some(&watch), &mut resolver, HOST, start);
gates.admit(Some(&watch), &mut resolver, HOST, Instant::now());
assert_eq!(
gates.admit(Some(&watch), &mut resolver, HOST, Instant::now()),
Admission::Unreachable
);
assert_eq!(gates.refusal(HOST), "no ARP reply");
}
}