use std::collections::{HashMap, HashSet, VecDeque};
use std::net::IpAddr;
use std::time::{Duration, Instant};
use crate::scanner::pacing::retry::{Due, ProbeLedger, Resolution, RetryPolicy};
type Ledger = ProbeLedger<IpAddr, ()>;
pub(super) const NDP_RETRY_POLICY: RetryPolicy = RetryPolicy::new(
2,
Duration::from_millis(800),
Duration::from_millis(400),
Duration::from_secs(3),
1.5,
0.2,
None,
)
.without_cross_host_estimate();
pub(super) const SOLICITATION_ATTEMPTS: u8 = 3;
pub(super) const SOLICITATION_INTERVAL: Duration = Duration::from_millis(600);
pub(super) const SOLICITATION_WINDOW: Duration = Duration::from_millis(1_500);
#[derive(Debug)]
pub(super) struct Solicitation {
pub(super) identifier: u16,
pub(super) sent_at: Vec<Instant>,
next_due: Option<Instant>,
last_sent_at: Option<Instant>,
}
impl Default for Solicitation {
fn default() -> Self {
Self {
identifier: rand::random(),
sent_at: Vec::with_capacity(SOLICITATION_ATTEMPTS as usize),
next_due: None,
last_sent_at: None,
}
}
}
impl Solicitation {
pub(super) fn next_sequence(&self) -> u16 {
self.sent_at.len() as u16
}
pub(super) fn sent_at(&self, identifier: u16, sequence: u16) -> Option<Instant> {
if identifier != self.identifier {
return None;
}
self.sent_at.get(sequence as usize).copied()
}
pub(super) fn arm(&mut self, now: Instant) {
self.next_due = Some(now);
}
pub(super) fn record_sent(&mut self, now: Instant) {
self.sent_at.push(now);
self.last_sent_at = Some(now);
self.next_due = (self.sent_at.len() < SOLICITATION_ATTEMPTS as usize)
.then(|| now + SOLICITATION_INTERVAL);
}
pub(super) fn is_due(&self, now: Instant) -> bool {
self.next_due.is_some_and(|due| due <= now)
}
pub(super) fn window_open(&self, now: Instant) -> bool {
if self.next_due.is_some() {
return true;
}
self.last_sent_at
.is_some_and(|sent_at| now < sent_at + SOLICITATION_WINDOW)
}
pub(super) fn nothing_sent(&self) -> bool {
self.sent_at.is_empty()
}
pub(super) fn next_wakeup(&self) -> Option<Instant> {
self.next_due.or_else(|| {
self.last_sent_at
.map(|sent_at| sent_at + SOLICITATION_WINDOW)
})
}
}
pub(super) struct Ipv6Discovery {
solicitation: Solicitation,
ledger: Ledger,
solicited: HashSet<IpAddr>,
confirming: VecDeque<IpAddr>,
confirmed_at: HashMap<IpAddr, Instant>,
first_asked_at: HashMap<IpAddr, Instant>,
}
impl Ipv6Discovery {
pub(super) fn new(capacity: usize) -> Self {
Self {
solicitation: Solicitation::default(),
ledger: Ledger::new(NDP_RETRY_POLICY, capacity),
solicited: HashSet::new(),
confirming: VecDeque::new(),
confirmed_at: HashMap::new(),
first_asked_at: HashMap::new(),
}
}
pub(super) fn solicitation(&self) -> &Solicitation {
&self.solicitation
}
pub(super) fn arm_solicitation(&mut self, now: Instant) {
self.solicitation.arm(now);
}
pub(super) fn record_solicitation_sent(&mut self, now: Instant) {
self.solicitation.record_sent(now);
}
pub(super) fn note_overheard(&mut self, address: IpAddr) -> bool {
if !self.solicited.insert(address) {
return false;
}
self.confirming.push_back(address);
true
}
pub(super) fn is_solicited(&self, address: &IpAddr) -> bool {
self.solicited.contains(address)
}
pub(super) fn next_confirmation(&mut self) -> Option<IpAddr> {
self.confirming.pop_front()
}
pub(super) fn confirmations_pending(&self) -> bool {
!self.confirming.is_empty()
}
pub(super) fn record_confirmation_sent(&mut self, address: IpAddr, now: Instant) {
self.confirmed_at.insert(address, now);
}
pub(super) fn take_confirmation_rtt(
&mut self,
address: &IpAddr,
now: Instant,
) -> Option<Duration> {
self.confirmed_at
.remove(address)
.map(|sent_at| now.saturating_duration_since(sent_at))
}
pub(super) fn unanswered_confirmations(&self) -> usize {
self.confirmed_at.len()
}
pub(super) fn record_asked(&mut self, address: IpAddr, now: Instant) {
self.solicited.insert(address);
self.first_asked_at.entry(address).or_insert(now);
self.ledger.arm(address, address, (), now);
}
pub(super) fn resolve(&mut self, address: &IpAddr, now: Instant) -> Option<Resolution> {
self.ledger.resolve(address, None, now)
}
pub(super) fn drain_due(&mut self, now: Instant, buf: &mut Vec<Due<IpAddr>>) {
self.ledger.drain_due(now, buf);
}
pub(super) fn since_first_asked(&self, address: &IpAddr, now: Instant) -> String {
match self.first_asked_at.get(address) {
Some(asked) => format!(
" ({}ms after it was first asked)",
now.saturating_duration_since(*asked).as_millis()
),
None => String::new(),
}
}
pub(super) fn is_idle(&self, now: Instant) -> bool {
self.confirming.is_empty()
&& self.ledger.is_empty()
&& !self.solicitation.window_open(now)
&& !self.confirmation_window_open(now)
}
fn confirmation_window_open(&self, now: Instant) -> bool {
self.confirmed_at
.values()
.any(|sent_at| now < *sent_at + SOLICITATION_WINDOW)
}
pub(super) fn next_wakeup(&self) -> Option<Instant> {
let confirmation = self
.confirmed_at
.values()
.map(|sent_at| *sent_at + SOLICITATION_WINDOW)
.min();
[
self.ledger.next_due(),
self.solicitation.next_wakeup(),
confirmation,
]
.into_iter()
.flatten()
.min()
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::scanner::pacing::retry::ProbeLedger;
const SLOWEST_MEASURED_ANSWER: Duration = Duration::from_millis(408);
#[test]
fn the_solicitation_schedule_outlasts_the_replies_without_the_sweep_paying_for_it() {
assert!(
NDP_RETRY_POLICY.initial_rto > SLOWEST_MEASURED_ANSWER,
"a first attempt must outlast the slowest answer measured, or the \
retry lands first and Karn's rule discards the sample"
);
assert!(
NDP_RETRY_POLICY.min_rto >= SLOWEST_MEASURED_ANSWER / 2,
"the floor is the schedule for every neighbour with no measurement \
of its own, so it cannot sit far below where the answers are"
);
assert!(
NDP_RETRY_POLICY.worst_case_probe_lifetime() < Duration::from_secs(3),
"the sweep's deadline is sized from this, so slack here is charged \
to every scan whether or not any IPv6 neighbour is slow"
);
}
#[test]
fn a_neighbours_schedule_is_not_inherited_from_a_faster_one() {
let router: IpAddr = "fe80::1".parse().unwrap();
let sleeper: IpAddr = "fe80::2".parse().unwrap();
let floor = NDP_RETRY_POLICY
.min_rto
.mul_f64(1.0 + NDP_RETRY_POLICY.jitter);
for seed in [1, 0x5EED, 0xC0FFEE, u64::MAX] {
let mut ledger: Ledger = ProbeLedger::seeded(NDP_RETRY_POLICY, 4, seed);
let start = Instant::now();
ledger.arm(router, router, (), start);
ledger.resolve(&router, None, start + Duration::from_millis(5));
ledger.arm(sleeper, sleeper, (), start);
let due = ledger.next_due().expect("the sleeper has a timer");
assert!(
due.saturating_duration_since(start) > floor,
"a router answering in 5 ms must not schedule the retry for a \
neighbour that has not answered at all (seed {seed})"
);
assert!(
due.saturating_duration_since(start) > SLOWEST_MEASURED_ANSWER,
"and the wait must still outlast the slowest answer measured \
(seed {seed})"
);
}
}
fn v6(last: u16) -> IpAddr {
IpAddr::V6(std::net::Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, last))
}
#[test]
fn an_address_asked_directly_is_never_also_confirmed() {
let mut ipv6 = Ipv6Discovery::new(4);
let target = v6(0xAA);
ipv6.record_asked(target, Instant::now());
assert!(
!ipv6.note_overheard(target),
"the address is already spoken for"
);
assert!(
!ipv6.confirmations_pending(),
"queueing a confirmation here sends a second identical solicitation"
);
}
#[test]
fn an_overheard_address_is_confirmed_exactly_once() {
let mut ipv6 = Ipv6Discovery::new(4);
let neighbour = v6(0xBB);
assert!(
ipv6.note_overheard(neighbour),
"the first sighting queues it"
);
for _ in 0..5 {
assert!(
!ipv6.note_overheard(neighbour),
"every later sighting is the same address"
);
}
assert_eq!(ipv6.next_confirmation(), Some(neighbour));
assert_eq!(ipv6.next_confirmation(), None, "one probe, not six");
}
#[test]
fn a_confirmations_round_trip_is_taken_once() {
let mut ipv6 = Ipv6Discovery::new(4);
let neighbour = v6(0xCC);
let sent = Instant::now();
ipv6.record_confirmation_sent(neighbour, sent);
let rtt = ipv6.take_confirmation_rtt(&neighbour, sent + Duration::from_millis(120));
assert_eq!(rtt, Some(Duration::from_millis(120)));
assert_eq!(
ipv6.take_confirmation_rtt(&neighbour, sent + Duration::from_millis(300)),
None,
"the probe it measured is already resolved"
);
}
#[test]
fn a_sweep_is_not_idle_while_a_confirmation_could_still_be_answered() {
let mut ipv6 = Ipv6Discovery::new(4);
let sent = Instant::now();
ipv6.record_confirmation_sent(v6(0xDD), sent);
assert!(
!ipv6.is_idle(sent + SOLICITATION_WINDOW / 2),
"the answer is still within its window"
);
assert!(
ipv6.is_idle(sent + SOLICITATION_WINDOW + Duration::from_millis(1)),
"past the window there is nothing left to wait for"
);
}
#[test]
fn the_next_wakeup_is_the_earliest_of_the_three_schedules() {
let mut ipv6 = Ipv6Discovery::new(4);
let now = Instant::now();
assert_eq!(ipv6.next_wakeup(), None, "nothing has been asked yet");
ipv6.record_confirmation_sent(v6(0xEE), now);
let confirmation_due = now + SOLICITATION_WINDOW;
assert_eq!(ipv6.next_wakeup(), Some(confirmation_due));
ipv6.arm_solicitation(now);
assert_eq!(
ipv6.next_wakeup(),
Some(now),
"a probe that is owed now outranks a window that closes later"
);
}
}