use super::timer::later;
use crate::config::{RetryConfig, ScanEffort};
use std::collections::{BinaryHeap, HashMap};
use std::hash::Hash;
use std::net::IpAddr;
use std::time::{Duration, Instant};
const MAX_TRACKED_ATTEMPTS: usize = 4;
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SilentHostPolicy {
pub threshold: u16,
pub reduced_attempts: u8,
}
impl SilentHostPolicy {
pub const fn new(threshold: u16, reduced_attempts: u8) -> Self {
Self {
threshold,
reduced_attempts,
}
}
}
#[must_use]
#[non_exhaustive]
#[derive(Debug, Clone, Copy)]
pub struct RetryPolicy {
pub max_attempts: u8,
pub initial_rto: Duration,
pub min_rto: Duration,
pub max_rto: Duration,
pub backoff: f64,
pub jitter: f64,
pub silent_host: Option<SilentHostPolicy>,
pub cross_host_estimate: bool,
}
impl RetryPolicy {
pub const fn new(
max_attempts: u8,
initial_rto: Duration,
min_rto: Duration,
max_rto: Duration,
backoff: f64,
jitter: f64,
silent_host: Option<SilentHostPolicy>,
) -> Self {
Self {
max_attempts,
initial_rto,
min_rto,
max_rto,
backoff,
jitter,
silent_host,
cross_host_estimate: true,
}
}
pub const fn without_cross_host_estimate(self) -> Self {
Self {
cross_host_estimate: false,
..self
}
}
pub const fn none() -> Self {
Self::new(
1,
Duration::from_millis(200),
Duration::from_millis(25),
Duration::from_secs(2),
2.0,
0.2,
None,
)
}
pub fn configured(self, config: RetryConfig) -> Self {
let mut policy = match config.effort {
ScanEffort::Single => Self {
max_attempts: 1,
..self
},
ScanEffort::Fast => Self {
max_attempts: self.max_attempts.saturating_sub(1).max(1),
..self
}
.scaled(0.6),
ScanEffort::Balanced => self,
ScanEffort::Thorough => Self {
max_attempts: self.max_attempts.saturating_add(2),
..self
}
.scaled(1.5),
};
if config.effort == ScanEffort::Thorough || !config.dampen_silent_hosts {
policy.silent_host = None;
}
if let Some(max_attempts) = config.max_attempts {
policy.max_attempts = max_attempts.get();
}
if let Some(scale) = config.timeout_scale {
policy = policy.scaled(scale.get());
}
policy
}
fn scaled(self, factor: f64) -> Self {
debug_assert!(
factor.is_finite() && factor > 0.0,
"a scale that cannot build a schedule is refused at `TimeoutScale`, \
and the effort levels below pass their own literals"
);
Self {
initial_rto: saturating_mul(self.initial_rto, factor),
max_rto: saturating_mul(self.max_rto, factor).max(self.min_rto),
..self
}
}
pub fn worst_case_probe_lifetime(&self) -> Duration {
let mut total = Duration::ZERO;
for attempt in 1..=self.max_attempts {
let scaled = scale(self.initial_rto, self.backoff, attempt, self.max_rto);
total = total.saturating_add(saturating_mul(scaled, 1.0 + self.jitter.max(0.0)));
}
total
}
pub(crate) fn longest_timeout(&self) -> Duration {
let ceiling = self.max_rto.max(self.min_rto);
saturating_mul(ceiling, 1.0 + self.jitter.clamp(0.0, 1.0))
}
pub(crate) fn longest_probe_lifetime(&self) -> Duration {
self.longest_timeout()
.saturating_mul(u32::from(self.max_attempts.max(1)))
}
fn budget_for(&self, host: Option<&HostState>) -> u8 {
let Some(rule) = self.silent_host else {
return self.max_attempts;
};
let Some(host) = host else {
return self.max_attempts;
};
if !host.answered && host.exhausted_silently >= rule.threshold {
return rule.reduced_attempts.min(self.max_attempts);
}
self.max_attempts
}
}
#[derive(Debug, Clone, Copy, Default)]
pub struct RttEstimator {
smoothed: Option<Duration>,
variation: Duration,
}
impl RttEstimator {
pub fn record(&mut self, sample: Duration) {
match self.smoothed {
None => {
self.smoothed = Some(sample);
self.variation = sample / 2;
}
Some(smoothed) => {
let deviation = smoothed.abs_diff(sample);
self.variation = (self.variation * 3 + deviation) / 4;
self.smoothed = Some((smoothed * 7 + sample) / 8);
}
}
}
pub fn timeout(&self) -> Option<Duration> {
self.smoothed
.map(|smoothed| smoothed.saturating_add(self.variation * 4))
}
pub fn is_empty(&self) -> bool {
self.smoothed.is_none()
}
}
#[derive(Debug, Clone, Copy)]
struct Attempt<T> {
token: T,
sent_at: Instant,
witnessed: bool,
}
struct Record<T, P> {
payload: P,
host: IpAddr,
attempts: [Option<Attempt<T>>; MAX_TRACKED_ATTEMPTS],
sends: u8,
witnessed: u8,
recorded: u8,
budget: u8,
generation: u32,
deferred: bool,
}
impl<T: Copy, P> Record<T, P> {
fn new(host: IpAddr, budget: u8, generation: u32, payload: P) -> Self {
Self {
payload,
host,
attempts: [None; MAX_TRACKED_ATTEMPTS],
sends: 1,
recorded: 0,
witnessed: 0,
budget,
generation,
deferred: false,
}
}
fn record_attempt(&mut self, token: T, sent_at: Instant) {
self.recorded = self.recorded.saturating_add(1);
let fresh = Attempt {
token,
sent_at,
witnessed: false,
};
if self.attempts[MAX_TRACKED_ATTEMPTS - 1].is_some() {
self.attempts.rotate_left(1);
self.attempts[MAX_TRACKED_ATTEMPTS - 1] = Some(fresh);
return;
}
let slot = self
.attempts
.iter()
.position(Option::is_none)
.unwrap_or(MAX_TRACKED_ATTEMPTS - 1);
self.attempts[slot] = Some(fresh);
}
fn witness(&mut self, token: &T) -> bool
where
T: PartialEq,
{
let Some(attempt) = self
.attempts
.iter_mut()
.flatten()
.find(|attempt| attempt.token == *token)
else {
return false;
};
if attempt.witnessed {
return false;
}
attempt.witnessed = true;
self.witnessed = self.witnessed.saturating_add(1);
true
}
fn attempt_of(&self, token: &T) -> Option<(u8, Instant)>
where
T: PartialEq,
{
let tracked = self.attempts.iter().flatten().count();
self.attempts
.iter()
.flatten()
.enumerate()
.find(|(_, attempt)| attempt.token == *token)
.map(|(slot, attempt)| {
let back_from_newest = (tracked - 1 - slot) as u8;
(
self.recorded.saturating_sub(back_from_newest),
attempt.sent_at,
)
})
}
fn unambiguous_sent_at(&self) -> Option<Instant> {
if self.sends != 1 {
return None;
}
self.attempts
.iter()
.flatten()
.next()
.map(|attempt| attempt.sent_at)
}
}
#[derive(Debug, Clone, Copy, Default)]
struct HostState {
estimator: RttEstimator,
outstanding: u32,
answered: bool,
exhausted_silently: u16,
}
struct Timer<K> {
due: Instant,
key: K,
generation: u32,
}
impl<K> PartialEq for Timer<K> {
fn eq(&self, other: &Self) -> bool {
self.due == other.due
}
}
impl<K> Eq for Timer<K> {}
impl<K> Ord for Timer<K> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other.due.cmp(&self.due)
}
}
impl<K> PartialOrd for Timer<K> {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Due<K, P = ()> {
Retry {
key: K,
attempt: u8,
},
Exhausted {
key: K,
payload: P,
attempts: u8,
witnessed: u8,
},
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Resolution<P = ()> {
pub payload: P,
pub rtt: Option<Duration>,
pub attempts: u8,
pub answered_attempt: Option<u8>,
}
pub struct ProbeLedger<K, T, P = ()> {
policy: RetryPolicy,
records: HashMap<K, Record<T, P>>,
timers: BinaryHeap<Timer<K>>,
hosts: HashMap<IpAddr, HostState>,
global: RttEstimator,
next_generation: u32,
jitter: Jitter,
}
impl<K, T, P> ProbeLedger<K, T, P>
where
K: Copy + Eq + Hash,
T: Copy + PartialEq,
P: Copy,
{
pub fn new(policy: RetryPolicy, capacity: usize) -> Self {
Self::seeded(policy, capacity, rand::random())
}
pub fn seeded(policy: RetryPolicy, capacity: usize, seed: u64) -> Self {
Self {
policy,
records: HashMap::with_capacity(capacity),
timers: BinaryHeap::with_capacity(capacity),
hosts: HashMap::new(),
global: RttEstimator::default(),
next_generation: 0,
jitter: Jitter::new(seed),
}
}
pub fn arm(&mut self, host: IpAddr, key: K, token: T, payload: P, now: Instant) {
self.arm_inner(host, key, token, Some(payload), now);
}
pub fn rearm(&mut self, host: IpAddr, key: K, token: T, now: Instant) {
self.arm_inner(host, key, token, None, now);
}
fn arm_inner(&mut self, host: IpAddr, key: K, token: T, payload: Option<P>, now: Instant) {
let generation = self.take_generation();
let host_state = self.hosts.entry(host).or_default();
let budget = self.policy.budget_for(Some(host_state));
let record = match self.records.get_mut(&key) {
Some(record) => {
record.budget = budget;
record.generation = generation;
record.deferred = false;
if let Some(payload) = payload {
record.payload = payload;
}
record
}
None => {
let Some(payload) = payload else {
return;
};
host_state.outstanding += 1;
self.records
.entry(key)
.or_insert_with(|| Record::new(host, budget, generation, payload))
}
};
record.record_attempt(token, now);
let attempt = record.sends;
let due = later(now, self.timeout_for(host, attempt));
self.timers.push(Timer {
due,
key,
generation,
});
}
pub fn resolve(&mut self, key: &K, token: Option<T>, now: Instant) -> Option<Resolution<P>> {
let record = self.records.get(key)?;
let payload = record.payload;
let attributed = match token {
Some(token) => Some(record.attempt_of(&token)?),
None => record.unambiguous_sent_at().map(|sent_at| (1, sent_at)),
};
let answered_attempt = attributed.map(|(ordinal, _)| ordinal);
let sent_at = attributed.map(|(_, sent_at)| sent_at);
let attempts = record.sends;
let host = record.host;
self.records.remove(key);
let rtt = sent_at.map(|sent_at| now.saturating_duration_since(sent_at));
let host_state = self.hosts.entry(host).or_default();
host_state.outstanding = host_state.outstanding.saturating_sub(1);
host_state.answered = true;
if let Some(rtt) = rtt {
host_state.estimator.record(rtt);
self.global.record(rtt);
}
Some(Resolution {
payload,
rtt,
attempts,
answered_attempt,
})
}
pub fn drain_due(&mut self, now: Instant, out: &mut Vec<Due<K, P>>) {
while let Some(timer) = self.timers.peek() {
if timer.due > now {
break;
}
let timer = self.timers.pop().expect("peeked");
let Some(record) = self.records.get_mut(&timer.key) else {
continue; };
if record.generation != timer.generation {
continue; }
if record.sends >= record.budget {
let host = record.host;
let attempts = record.sends;
let witnessed = record.witnessed;
let payload = record.payload;
self.records.remove(&timer.key);
self.retire(host);
out.push(Due::Exhausted {
key: timer.key,
payload,
attempts,
witnessed,
});
continue;
}
record.sends += 1;
let attempt = record.sends;
let host = record.host;
let generation = self.take_generation();
self.records
.get_mut(&timer.key)
.expect("record present")
.generation = generation;
let due = later(now, self.timeout_for(host, attempt));
self.timers.push(Timer {
due,
key: timer.key,
generation,
});
out.push(Due::Retry {
key: timer.key,
attempt,
});
}
}
pub fn next_due(&self) -> Option<Instant> {
self.timers.peek().map(|timer| timer.due)
}
pub(crate) fn defer(&mut self, key: &K) {
let generation = self.take_generation();
if let Some(record) = self.records.get_mut(key) {
record.generation = generation;
record.deferred = true;
}
}
pub(crate) fn resume(&mut self, key: &K, now: Instant) {
let Some(record) = self.records.get(key) else {
return;
};
if !record.deferred {
return;
}
let (host, attempt) = (record.host, record.sends);
let due = later(now, self.timeout_for(host, attempt));
let generation = self.take_generation();
let record = self.records.get_mut(key).expect("present above");
record.deferred = false;
record.generation = generation;
self.timers.push(Timer {
due,
key: *key,
generation,
});
}
pub fn drain_unresolved(&mut self) -> Vec<K> {
self.timers.clear();
let keys: Vec<K> = self.records.keys().copied().collect();
self.records.clear();
for host in self.hosts.values_mut() {
host.outstanding = 0;
}
keys
}
pub fn len(&self) -> usize {
self.records.len()
}
pub fn is_empty(&self) -> bool {
self.records.is_empty()
}
pub fn witness(&mut self, key: &K, token: &T) -> bool
where
T: PartialEq,
{
self.records
.get_mut(key)
.is_some_and(|record| record.witness(token))
}
pub fn contains(&self, key: &K) -> bool {
self.records.contains_key(key)
}
pub fn names_attempt(&self, key: &K, token: Option<&T>) -> bool {
let Some(record) = self.records.get(key) else {
return false;
};
match token {
Some(token) => record.attempt_of(token).is_some(),
None => true,
}
}
pub fn host_has_answered(&self, host: &IpAddr) -> bool {
self.hosts.get(host).is_some_and(|state| state.answered)
}
pub fn host_rtt(&self, host: &IpAddr) -> Option<Duration> {
self.hosts.get(host)?.estimator.smoothed
}
pub fn seed_host_rtt(&mut self, host: IpAddr, rtt: Duration) {
let state = self.hosts.entry(host).or_default();
if state.estimator.is_empty() {
state.estimator.record(rtt);
}
if self.policy.cross_host_estimate && self.global.is_empty() {
self.global.record(rtt);
}
}
fn retire(&mut self, host: IpAddr) {
let state = self.hosts.entry(host).or_default();
state.outstanding = state.outstanding.saturating_sub(1);
if !state.answered {
state.exhausted_silently = state.exhausted_silently.saturating_add(1);
}
}
fn timeout_for(&mut self, host: IpAddr, attempt: u8) -> Duration {
let measured = self
.hosts
.get(&host)
.and_then(|state| state.estimator.timeout())
.or_else(|| {
self.policy
.cross_host_estimate
.then(|| self.global.timeout())
.flatten()
});
let ceiling = self.policy.max_rto.max(self.policy.min_rto);
let base = match measured {
Some(measured) => measured,
None => self.policy.initial_rto,
};
let base = base.clamp(self.policy.min_rto, ceiling);
let scaled = scale(base, self.policy.backoff, attempt, ceiling);
self.jitter.spread(scaled, self.policy.jitter)
}
fn take_generation(&mut self) -> u32 {
self.next_generation = self.next_generation.wrapping_add(1);
self.next_generation
}
}
fn scale(base: Duration, backoff: f64, attempt: u8, ceiling: Duration) -> Duration {
if attempt <= 1 || backoff <= 1.0 {
return base.min(ceiling);
}
saturating_mul(base, backoff.powi(i32::from(attempt - 1))).min(ceiling)
}
pub(crate) fn saturating_mul(duration: Duration, factor: f64) -> Duration {
let seconds = duration.as_secs_f64() * factor;
Duration::try_from_secs_f64(seconds).unwrap_or(if seconds > 0.0 {
Duration::MAX
} else {
Duration::ZERO
})
}
struct Jitter(u64);
impl Jitter {
fn new(seed: u64) -> Self {
Self(seed)
}
fn next_u64(&mut self) -> u64 {
self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
let mut z = self.0;
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
fn next_unit(&mut self) -> f64 {
(self.next_u64() >> 11) as f64 / (1u64 << 53) as f64
}
fn spread(&mut self, base: Duration, spread: f64) -> Duration {
if spread <= 0.0 {
return base;
}
let spread = spread.min(1.0);
let factor = 1.0 + (self.next_unit() * 2.0 - 1.0) * spread;
saturating_mul(base, factor.max(0.0))
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::config::TimeoutScale;
use std::net::Ipv4Addr;
use std::num::NonZeroU8;
const HOST: IpAddr = IpAddr::V4(Ipv4Addr::new(192, 0, 2, 200));
const OTHER: IpAddr = IpAddr::V4(Ipv4Addr::new(192, 0, 2, 201));
fn policy() -> RetryPolicy {
RetryPolicy::new(
3,
Duration::from_millis(100),
Duration::from_millis(10),
Duration::from_secs(2),
1.0,
0.0,
None,
)
}
fn schedule_to_the_end(policy: RetryPolicy) -> u8 {
let _ = (
policy.worst_case_probe_lifetime(),
policy.longest_probe_lifetime(),
);
let mut ledger = ledger(policy);
ledger.arm(HOST, (HOST, 80), 0, (), Instant::now());
while let Some(now) = ledger.next_due() {
for event in due_at(&mut ledger, now) {
match event {
Due::Retry { key, attempt } => {
ledger.rearm(HOST, key, u32::from(attempt), now);
}
Due::Exhausted { attempts, .. } => return attempts,
}
}
}
0
}
#[test]
fn every_attempt_budget_a_caller_can_ask_for_schedules_without_panicking() {
for backoff in [2.0, 3.0] {
let policy = RetryPolicy {
backoff,
..policy()
}
.configured(RetryConfig {
max_attempts: std::num::NonZeroU8::new(u8::MAX),
..RetryConfig::default()
});
assert_eq!(schedule_to_the_end(policy), u8::MAX, "backoff {backoff}");
}
}
#[test]
fn the_largest_timeout_scale_schedules_without_panicking() {
let policy = policy().configured(RetryConfig {
timeout_scale: TimeoutScale::new(f64::MAX),
..RetryConfig::default()
});
assert!(policy.max_rto >= Duration::from_secs(u64::from(u32::MAX)));
let now = Instant::now();
let mut ledger = ledger(policy);
ledger.arm(HOST, (HOST, 80), 0, (), now);
assert!(
due_at(&mut ledger, now + Duration::from_secs(3600)).is_empty(),
"a timeout that long is not due within the hour"
);
}
fn ledger(policy: RetryPolicy) -> ProbeLedger<(IpAddr, u16), u32> {
ProbeLedger::seeded(policy, 8, 0x5EED)
}
#[test]
fn a_seeded_host_is_timed_from_the_measurement_rather_than_the_guess() {
let mut ledger = ledger(policy());
let unseeded = ledger.timeout_for(OTHER, 1);
assert_eq!(
unseeded,
Duration::from_millis(100),
"with nothing measured, the policy's starting timeout stands"
);
ledger.seed_host_rtt(HOST, Duration::from_millis(5));
assert!(
ledger.timeout_for(HOST, 1) < unseeded,
"a host already known to answer in five milliseconds is not worth \
a hundred of patience"
);
}
#[test]
fn seeding_does_not_overwrite_what_the_scan_has_measured() {
let mut ledger = ledger(policy());
let start = Instant::now();
ledger.arm(HOST, (HOST, 80), 1, (), start);
ledger.resolve(&(HOST, 80), Some(1), start + Duration::from_millis(40));
let measured = ledger.host_rtt(&HOST);
ledger.seed_host_rtt(HOST, Duration::from_millis(1));
assert_eq!(ledger.host_rtt(&HOST), measured);
}
#[test]
fn one_hosts_round_trip_does_not_time_another_when_the_policy_forbids_it() {
let policy = RetryPolicy::new(
2,
Duration::from_millis(800),
Duration::from_millis(50),
Duration::from_secs(3),
1.5,
0.0,
None,
)
.without_cross_host_estimate();
let fast: IpAddr = "192.0.2.1".parse().unwrap();
let unmeasured: IpAddr = "192.0.2.2".parse().unwrap();
let start = Instant::now();
let mut ledger = ledger(policy);
ledger.arm(fast, (fast, 0), 1, (), start);
let resolved = ledger
.resolve(&(fast, 0), Some(1), start + Duration::from_millis(6))
.expect("the fast host resolves");
assert_eq!(resolved.rtt, Some(Duration::from_millis(6)));
ledger.arm(unmeasured, (unmeasured, 0), 1, (), start);
let due = ledger.next_due().expect("a timer for the unmeasured host");
assert_eq!(
due.saturating_duration_since(start),
Duration::from_millis(800),
"the unmeasured host must be timed by the policy's own initial timeout, not by what a different host happened to answer in"
);
}
#[test]
fn one_hosts_round_trip_times_another_by_default() {
let policy = RetryPolicy::new(
2,
Duration::from_millis(800),
Duration::from_millis(50),
Duration::from_secs(3),
1.5,
0.0,
None,
);
let fast: IpAddr = "192.0.2.1".parse().unwrap();
let unmeasured: IpAddr = "192.0.2.2".parse().unwrap();
let start = Instant::now();
let mut ledger = ledger(policy);
ledger.arm(fast, (fast, 0), 1, (), start);
ledger.resolve(&(fast, 0), Some(1), start + Duration::from_millis(6));
ledger.arm(unmeasured, (unmeasured, 0), 1, (), start);
let due = ledger.next_due().expect("a timer for the unmeasured host");
assert!(
due.saturating_duration_since(start) < Duration::from_millis(800),
"a measured path should shorten the wait for a target that has not answered yet"
);
}
fn due_at(
ledger: &mut ProbeLedger<(IpAddr, u16), u32>,
now: Instant,
) -> Vec<Due<(IpAddr, u16)>> {
let mut out = Vec::new();
ledger.drain_due(now, &mut out);
out
}
#[test]
fn a_reply_names_the_attempt_it_answers_not_the_number_sent() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let t1 = t0 + Duration::from_millis(100);
due_at(&mut ledger, t1);
ledger.arm(HOST, (HOST, 80), 2, (), t1);
let t2 = t1 + Duration::from_millis(100);
due_at(&mut ledger, t2);
ledger.arm(HOST, (HOST, 80), 3, (), t2);
let resolution = ledger
.resolve(&(HOST, 80), Some(1), t2 + Duration::from_millis(50))
.expect("a live token resolves");
assert_eq!(resolution.answered_attempt, Some(1));
assert_eq!(resolution.attempts, 3, "three sends had been charged");
assert_eq!(resolution.rtt, Some(Duration::from_millis(250)));
}
#[test]
fn a_reply_to_the_latest_attempt_is_numbered_and_measured_by_it() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let t1 = t0 + Duration::from_millis(100);
due_at(&mut ledger, t1);
ledger.arm(HOST, (HOST, 80), 2, (), t1);
let resolution = ledger
.resolve(&(HOST, 80), Some(2), t1 + Duration::from_millis(5))
.expect("a live token resolves");
assert_eq!(resolution.answered_attempt, Some(2));
assert_eq!(
resolution.rtt,
Some(Duration::from_millis(5)),
"measured from the second attempt, not the 105ms since the first"
);
}
#[test]
fn an_untokened_reply_is_attributed_only_when_one_send_has_happened() {
let t0 = Instant::now();
let mut once = ledger(policy());
once.arm(HOST, (HOST, 80), 1, (), t0);
let single = once
.resolve(&(HOST, 80), None, t0 + Duration::from_millis(10))
.expect("resolves");
assert_eq!(single.answered_attempt, Some(1));
let mut twice = ledger(policy());
twice.arm(OTHER, (OTHER, 80), 1, (), t0);
let t1 = t0 + Duration::from_millis(100);
due_at(&mut twice, t1);
twice.arm(OTHER, (OTHER, 80), 2, (), t1);
let retried = twice
.resolve(&(OTHER, 80), None, t1 + Duration::from_millis(10))
.expect("resolves");
assert_eq!(retried.answered_attempt, None);
assert_eq!(retried.rtt, None);
}
#[test]
fn attempts_stay_correctly_numbered_after_the_oldest_tokens_are_evicted() {
let sends = 6;
let t0 = Instant::now();
let generous = RetryPolicy::new(
8,
Duration::from_millis(100),
Duration::from_millis(10),
Duration::from_secs(2),
1.0,
0.0,
None,
);
let sent_six = |t0: Instant| {
let mut ledger = ledger(generous);
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let mut now = t0;
for token in 2..=sends {
now += Duration::from_millis(100);
due_at(&mut ledger, now);
ledger.arm(HOST, (HOST, 80), token, (), now);
}
(ledger, now)
};
let (mut ledger, now) = sent_six(t0);
let newest = ledger
.resolve(&(HOST, 80), Some(sends), now + Duration::from_millis(5))
.expect("resolves");
assert_eq!(newest.answered_attempt, Some(6));
let (mut ledger, now) = sent_six(t0);
let oldest_retained = ledger
.resolve(&(HOST, 80), Some(3), now + Duration::from_millis(5))
.expect("resolves");
assert_eq!(
oldest_retained.answered_attempt,
Some(3),
"numbering counts back from the newest, not from the first slot"
);
let (mut ledger, now) = sent_six(t0);
assert!(
ledger
.resolve(&(HOST, 80), Some(1), now + Duration::from_millis(5))
.is_none()
);
}
#[test]
fn an_armed_probe_is_not_due_before_its_timeout() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
assert!(due_at(&mut ledger, t0 + Duration::from_millis(99)).is_empty());
assert_eq!(ledger.len(), 1);
}
#[test]
fn a_probe_is_retried_when_its_timeout_passes() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let due = due_at(&mut ledger, t0 + Duration::from_millis(100));
assert_eq!(
due,
vec![Due::Retry {
key: (HOST, 80),
attempt: 2
}]
);
assert_eq!(ledger.len(), 1, "a retried probe is still outstanding");
}
#[test]
fn a_deferred_retry_stops_its_probes_clock_until_it_is_sent() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
assert_eq!(
due_at(&mut ledger, t0 + Duration::from_millis(100)).len(),
1
);
ledger.defer(&(HOST, 80));
assert!(
due_at(&mut ledger, t0 + Duration::from_secs(3600)).is_empty(),
"nothing comes due while the retry waits"
);
assert!(ledger.contains(&(HOST, 80)));
let sent = t0 + Duration::from_secs(3600);
ledger.rearm(HOST, (HOST, 80), 2, sent);
ledger.resume(&(HOST, 80), sent);
assert_eq!(
due_at(&mut ledger, sent + Duration::from_secs(10)),
vec![Due::Retry {
key: (HOST, 80),
attempt: 3
}],
"the next attempt is timed from the send, and only once"
);
}
#[test]
fn a_deferred_retry_that_is_not_sent_still_runs_its_probe_out() {
let t0 = Instant::now();
let mut ledger = ledger(RetryPolicy {
max_attempts: 2,
..policy()
});
ledger.arm(HOST, (HOST, 80), 1, (), t0);
assert_eq!(
due_at(&mut ledger, t0 + Duration::from_millis(100)).len(),
1
);
ledger.defer(&(HOST, 80));
let refused = t0 + Duration::from_secs(1);
ledger.resume(&(HOST, 80), refused);
assert!(matches!(
due_at(&mut ledger, refused + Duration::from_secs(10))[..],
[Due::Exhausted { attempts: 2, .. }]
));
}
#[test]
fn a_probe_exhausts_after_exactly_its_budget() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let mut sends = 1;
let mut exhausted = None;
for step in 1..10 {
let now = t0 + Duration::from_millis(100 * step);
for event in due_at(&mut ledger, now) {
match event {
Due::Retry { key, attempt } => {
sends += 1;
assert_eq!(attempt, sends);
ledger.rearm(HOST, key, attempt.into(), now);
}
Due::Exhausted { key, .. } => exhausted = Some(key),
}
}
}
assert_eq!(sends, 3, "one initial attempt plus two retries");
assert_eq!(exhausted, Some((HOST, 80)));
assert!(ledger.is_empty());
}
#[test]
fn a_single_attempt_policy_exhausts_without_ever_retrying() {
let t0 = Instant::now();
let mut ledger = ledger(RetryPolicy::none());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let due = due_at(&mut ledger, t0 + Duration::from_secs(5));
assert_eq!(
due,
vec![Due::Exhausted {
key: (HOST, 80),
payload: (),
attempts: 1,
witnessed: 0,
}]
);
}
#[test]
fn backoff_lengthens_each_successive_timeout() {
let t0 = Instant::now();
let policy = RetryPolicy::new(
4,
Duration::from_millis(100),
Duration::from_millis(10),
Duration::from_secs(10),
2.0,
0.0,
None,
);
let mut ledger = ledger(policy);
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let first = ledger.next_due().unwrap();
let due = due_at(&mut ledger, first);
assert!(matches!(due.as_slice(), [Due::Retry { .. }]));
let second = ledger.next_due().unwrap();
assert_eq!(
first.saturating_duration_since(t0),
Duration::from_millis(100)
);
assert_eq!(
second.saturating_duration_since(first),
Duration::from_millis(200)
);
}
#[test]
fn nothing_is_due_and_no_deadline_exists_on_an_empty_ledger() {
let mut ledger = ledger(policy());
assert!(ledger.next_due().is_none());
assert!(due_at(&mut ledger, Instant::now()).is_empty());
assert!(ledger.is_empty());
}
#[test]
fn a_matching_token_resolves_the_probe_and_measures_it() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 7, (), t0);
let resolved = ledger
.resolve(&(HOST, 80), Some(7), t0 + Duration::from_millis(12))
.expect("outstanding probe resolves");
assert_eq!(resolved.rtt, Some(Duration::from_millis(12)));
assert_eq!(resolved.attempts, 1);
assert!(ledger.is_empty());
}
#[test]
fn a_second_reply_resolves_nothing() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 7, (), t0);
assert!(ledger.resolve(&(HOST, 80), Some(7), t0).is_some());
assert!(ledger.resolve(&(HOST, 80), Some(7), t0).is_none());
}
#[test]
fn a_token_matching_no_attempt_leaves_the_probe_outstanding() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 7, (), t0);
assert!(ledger.resolve(&(HOST, 80), Some(999), t0).is_none());
assert_eq!(ledger.len(), 1, "someone else's packet resolves nothing");
}
#[test]
fn a_late_reply_to_an_earlier_attempt_still_resolves_the_probe() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 7, (), t0);
let retry = t0 + Duration::from_millis(100);
assert!(!due_at(&mut ledger, retry).is_empty());
ledger.arm(HOST, (HOST, 80), 8, (), retry);
let resolved = ledger
.resolve(&(HOST, 80), Some(7), t0 + Duration::from_millis(140))
.expect("the first attempt's answer is still an answer");
assert_eq!(
resolved.rtt,
Some(Duration::from_millis(140)),
"measured against the attempt that was actually answered"
);
assert_eq!(resolved.attempts, 2);
}
#[test]
fn an_unattributable_reply_resolves_without_measuring() {
let t0 = Instant::now();
let mut ledger: ProbeLedger<(IpAddr, u16), ()> = ProbeLedger::seeded(policy(), 8, 1);
ledger.arm(HOST, (HOST, 53), (), (), t0);
let retry = t0 + Duration::from_millis(100);
let mut out = Vec::new();
ledger.drain_due(retry, &mut out);
ledger.arm(HOST, (HOST, 53), (), (), retry);
let resolved = ledger
.resolve(&(HOST, 53), None, retry + Duration::from_millis(5))
.expect("resolves");
assert_eq!(resolved.rtt, None, "which attempt did it answer?");
assert_eq!(resolved.attempts, 2);
}
#[test]
fn an_unattributable_reply_to_a_single_attempt_is_still_measured() {
let t0 = Instant::now();
let mut ledger: ProbeLedger<(IpAddr, u16), ()> = ProbeLedger::seeded(policy(), 8, 1);
ledger.arm(HOST, (HOST, 53), (), (), t0);
let resolved = ledger
.resolve(&(HOST, 53), None, t0 + Duration::from_millis(9))
.expect("resolves");
assert_eq!(resolved.rtt, Some(Duration::from_millis(9)));
}
#[test]
fn a_resolved_probe_is_never_due_again() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 7, (), t0);
ledger.resolve(&(HOST, 80), Some(7), t0 + Duration::from_millis(5));
assert!(due_at(&mut ledger, t0 + Duration::from_secs(10)).is_empty());
}
#[test]
fn re_arming_supersedes_the_previous_timer() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let retry = t0 + Duration::from_millis(100);
assert_eq!(due_at(&mut ledger, retry).len(), 1);
ledger.arm(HOST, (HOST, 80), 2, (), retry);
let due = due_at(&mut ledger, retry + Duration::from_millis(1));
assert!(due.is_empty(), "stale timer fired: {due:?}");
}
#[test]
fn the_first_timeout_uses_the_initial_value_not_the_floor() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
assert_eq!(
ledger.next_due().unwrap().saturating_duration_since(t0),
Duration::from_millis(100),
"an unmeasured path is unknown, not known to be fast"
);
}
#[test]
fn a_measured_host_gets_a_timeout_derived_from_its_own_round_trip() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
ledger.resolve(&(HOST, 80), Some(1), t0 + Duration::from_millis(4));
ledger.arm(HOST, (HOST, 81), 2, (), t0);
let measured = ledger.next_due().unwrap().saturating_duration_since(t0);
assert_eq!(measured, Duration::from_millis(12));
assert_eq!(ledger.host_rtt(&HOST), Some(Duration::from_millis(4)));
}
#[test]
fn a_fast_host_does_not_shorten_a_different_hosts_timeout() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0);
ledger.resolve(&(HOST, 80), Some(1), t0 + Duration::from_millis(1));
ledger.arm(OTHER, (OTHER, 80), 2, (), t0);
let other = ledger.next_due().unwrap().saturating_duration_since(t0);
assert!(
other >= Duration::from_millis(3),
"an unmeasured host inherited a fast host's timing: {other:?}"
);
assert!(ledger.host_rtt(&OTHER).is_none());
}
#[test]
fn a_measured_timeout_is_held_above_the_floor() {
let t0 = Instant::now();
let mut policy = policy();
policy.min_rto = Duration::from_millis(50);
let mut ledger = ledger(policy);
ledger.arm(HOST, (HOST, 80), 1, (), t0);
ledger.resolve(&(HOST, 80), Some(1), t0 + Duration::from_micros(100));
ledger.arm(HOST, (HOST, 81), 2, (), t0);
assert_eq!(
ledger.next_due().unwrap().saturating_duration_since(t0),
Duration::from_millis(50)
);
}
#[test]
fn backed_off_timeouts_are_capped() {
let t0 = Instant::now();
let policy = RetryPolicy::new(
5,
Duration::from_millis(100),
Duration::from_millis(10),
Duration::from_millis(150),
10.0,
0.0,
None,
);
let mut ledger = ledger(policy);
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let first = ledger.next_due().unwrap();
due_at(&mut ledger, first);
let second = ledger.next_due().unwrap();
assert_eq!(
second.saturating_duration_since(first),
Duration::from_millis(150),
"backoff must not escape the ceiling"
);
}
#[test]
fn jitter_stays_within_its_stated_fraction() {
let policy = RetryPolicy::new(
2,
Duration::from_millis(100),
Duration::from_millis(10),
Duration::from_secs(2),
1.0,
0.25,
None,
);
for seed in 0..64u64 {
let t0 = Instant::now();
let mut ledger: ProbeLedger<(IpAddr, u16), u32> = ProbeLedger::seeded(policy, 4, seed);
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let due = ledger.next_due().unwrap().saturating_duration_since(t0);
assert!(
due >= Duration::from_millis(75) && due <= Duration::from_millis(125),
"seed {seed} produced {due:?}"
);
}
}
#[test]
fn jitter_decorrelates_probes_armed_together() {
let t0 = Instant::now();
let policy = RetryPolicy::new(
2,
Duration::from_millis(100),
Duration::from_millis(10),
Duration::from_secs(2),
1.0,
0.25,
None,
);
let mut ledger = ledger(policy);
for port in 0..64u16 {
ledger.arm(HOST, (HOST, port), u32::from(port), (), t0);
}
let due = due_at(&mut ledger, t0 + Duration::from_millis(100));
assert!(
due.len() < 64,
"every probe came due at once despite jitter"
);
assert!(
!due.is_empty(),
"jitter delayed everything past its own bound"
);
}
fn silent_policy() -> RetryPolicy {
RetryPolicy::new(
3,
Duration::from_millis(100),
Duration::from_millis(10),
Duration::from_secs(2),
1.0,
0.0,
Some(SilentHostPolicy::new(2, 1)),
)
}
fn spend(ledger: &mut ProbeLedger<(IpAddr, u16), u32>, host: IpAddr, port: u16) -> u8 {
let mut now = Instant::now();
ledger.arm(host, (host, port), 1, (), now);
let mut sends = 1;
for _ in 0..10 {
now += Duration::from_secs(1);
for event in due_at(ledger, now) {
match event {
Due::Retry { key, .. } => {
sends += 1;
ledger.arm(host, key, u32::from(sends), (), now);
}
Due::Exhausted { .. } => return sends,
}
}
}
panic!("probe never exhausted");
}
#[test]
fn a_host_that_never_answers_has_its_budget_cut_after_the_threshold() {
let mut ledger = ledger(silent_policy());
assert_eq!(spend(&mut ledger, HOST, 80), 3);
assert_eq!(spend(&mut ledger, HOST, 81), 3);
assert_eq!(
spend(&mut ledger, HOST, 82),
1,
"two probes spent in silence is the declared threshold"
);
}
#[test]
fn one_answer_of_any_kind_preserves_the_full_budget() {
let t0 = Instant::now();
let mut ledger = ledger(silent_policy());
assert_eq!(spend(&mut ledger, HOST, 80), 3);
assert_eq!(spend(&mut ledger, HOST, 81), 3);
ledger.arm(HOST, (HOST, 22), 9, (), t0);
ledger.resolve(&(HOST, 22), Some(9), t0 + Duration::from_millis(3));
assert_eq!(
spend(&mut ledger, HOST, 82),
3,
"the host proved it is there"
);
}
#[test]
fn one_silent_host_does_not_cut_another_hosts_budget() {
let mut ledger = ledger(silent_policy());
assert_eq!(spend(&mut ledger, HOST, 80), 3);
assert_eq!(spend(&mut ledger, HOST, 81), 3);
assert_eq!(spend(&mut ledger, HOST, 82), 1);
assert_eq!(spend(&mut ledger, OTHER, 80), 3);
}
#[test]
fn without_the_rule_a_silent_host_keeps_its_full_budget_forever() {
let mut ledger = ledger(policy());
for port in 80..90 {
assert_eq!(spend(&mut ledger, HOST, port), 3);
}
}
#[test]
fn draining_the_unresolved_empties_the_ledger() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
for port in 0..5u16 {
ledger.arm(HOST, (HOST, port), u32::from(port), (), t0);
}
let mut remaining = ledger.drain_unresolved();
remaining.sort_unstable();
assert_eq!(remaining.len(), 5);
assert!(ledger.is_empty());
assert!(ledger.next_due().is_none());
assert!(due_at(&mut ledger, t0 + Duration::from_secs(10)).is_empty());
}
#[test]
fn the_earliest_deadline_is_the_one_reported() {
let t0 = Instant::now();
let mut ledger = ledger(policy());
ledger.arm(HOST, (HOST, 80), 1, (), t0 + Duration::from_millis(50));
ledger.arm(HOST, (HOST, 81), 2, (), t0);
assert_eq!(
ledger.next_due().unwrap().saturating_duration_since(t0),
Duration::from_millis(100),
"the probe armed first comes due first"
);
}
#[test]
fn a_budget_beyond_the_tracked_attempts_keeps_the_newest_tokens() {
let t0 = Instant::now();
let policy = RetryPolicy::new(
8,
Duration::from_millis(100),
Duration::from_millis(10),
Duration::from_secs(2),
1.0,
0.0,
None,
);
let mut ledger = ledger(policy);
let mut now = t0;
ledger.arm(HOST, (HOST, 80), 1, (), now);
for token in 2..=7u32 {
now += Duration::from_millis(100);
assert!(!due_at(&mut ledger, now).is_empty());
ledger.arm(HOST, (HOST, 80), token, (), now);
}
assert!(
ledger.resolve(&(HOST, 80), Some(7), now).is_some(),
"the newest attempt must always be matchable"
);
}
#[test]
fn worst_case_lifetime_covers_every_attempt() {
let policy = RetryPolicy::new(
3,
Duration::from_millis(200),
Duration::from_millis(25),
Duration::from_secs(2),
2.0,
0.0,
None,
);
assert_eq!(
policy.worst_case_probe_lifetime(),
Duration::from_millis(1_400)
);
assert_eq!(
RetryPolicy::none().worst_case_probe_lifetime(),
Duration::from_millis(240),
"one attempt, jittered upward"
);
}
fn rate_limited_policy() -> RetryPolicy {
RetryPolicy::new(
2,
Duration::from_millis(1_500),
Duration::from_millis(1_200),
Duration::from_secs(5),
1.5,
0.0,
Some(SilentHostPolicy::new(32, 1)),
)
}
fn effort(effort: ScanEffort) -> RetryConfig {
RetryConfig {
effort,
..Default::default()
}
}
#[test]
fn the_default_configuration_changes_nothing() {
let base = policy();
let configured = base.configured(RetryConfig::default());
assert_eq!(configured.max_attempts, base.max_attempts);
assert_eq!(configured.initial_rto, base.initial_rto);
assert_eq!(configured.min_rto, base.min_rto);
assert_eq!(configured.max_rto, base.max_rto);
assert!(configured.silent_host.is_none(), "as the base had none");
}
#[test]
fn a_single_attempt_effort_disables_retransmission() {
let configured = policy().configured(effort(ScanEffort::Single));
assert_eq!(configured.max_attempts, 1);
}
#[test]
fn effort_moves_the_budget_in_the_direction_it_says() {
let base = policy();
let fast = base.configured(effort(ScanEffort::Fast));
let thorough = base.configured(effort(ScanEffort::Thorough));
assert!(fast.max_attempts < base.max_attempts);
assert!(thorough.max_attempts > base.max_attempts);
assert!(fast.initial_rto < base.initial_rto);
assert!(thorough.initial_rto > base.initial_rto);
}
#[test]
fn effort_never_reduces_the_budget_below_one_attempt() {
let base = RetryPolicy::none();
assert_eq!(base.max_attempts, 1);
assert_eq!(
base.configured(effort(ScanEffort::Fast)).max_attempts,
1,
"there is no such thing as sending a probe zero times"
);
}
#[test]
fn hurrying_a_scan_never_lowers_the_protocol_floor() {
let base = rate_limited_policy();
for config in [
effort(ScanEffort::Fast),
RetryConfig {
timeout_scale: TimeoutScale::new(0.1),
..Default::default()
},
RetryConfig {
effort: ScanEffort::Fast,
timeout_scale: TimeoutScale::new(0.01),
..Default::default()
},
] {
let configured = base.configured(config);
assert_eq!(
configured.min_rto, base.min_rto,
"the floor is what the protocol costs, not a preference"
);
}
}
#[test]
fn scaling_never_leaves_the_ceiling_below_the_floor() {
let configured = rate_limited_policy().configured(RetryConfig {
timeout_scale: TimeoutScale::new(0.01),
..Default::default()
});
assert!(configured.max_rto >= configured.min_rto);
assert!(configured.worst_case_probe_lifetime() > Duration::ZERO);
}
#[test]
fn a_scaled_down_start_is_still_held_above_the_floor() {
let t0 = Instant::now();
let base = rate_limited_policy();
let configured = base.configured(RetryConfig {
timeout_scale: TimeoutScale::new(0.1),
..Default::default()
});
assert!(configured.initial_rto < configured.min_rto, "test premise");
let mut ledger: ProbeLedger<(IpAddr, u16), ()> = ProbeLedger::seeded(configured, 4, 3);
ledger.arm(HOST, (HOST, 53), (), (), t0);
assert_eq!(
ledger.next_due().unwrap().saturating_duration_since(t0),
base.min_rto
);
}
#[test]
fn an_explicit_budget_overrides_the_effort_level() {
let configured = policy().configured(RetryConfig {
effort: ScanEffort::Thorough,
max_attempts: NonZeroU8::new(2),
..Default::default()
});
assert_eq!(configured.max_attempts, 2);
}
#[test]
fn one_attempt_seen_twice_is_witnessed_once() {
let mut ledger: ProbeLedger<(IpAddr, u16), u32> =
ProbeLedger::new(rate_limited_policy(), 8);
let t0 = Instant::now();
ledger.arm(HOST, (HOST, 80), 7, (), t0);
assert!(ledger.witness(&(HOST, 80), &7), "the first sighting counts");
assert!(
!ledger.witness(&(HOST, 80), &7),
"the second is the same one"
);
}
#[test]
fn a_sighting_of_something_else_witnesses_nothing() {
let mut ledger: ProbeLedger<(IpAddr, u16), u32> =
ProbeLedger::new(rate_limited_policy(), 8);
let t0 = Instant::now();
ledger.arm(HOST, (HOST, 80), 7, (), t0);
assert!(!ledger.witness(&(HOST, 80), &9), "a nonce nobody sent");
assert!(
!ledger.witness(&(HOST, 81), &7),
"a port nothing is armed on"
);
}
#[test]
fn an_exhausted_probe_reports_how_many_of_its_sends_were_seen() {
let mut ledger: ProbeLedger<(IpAddr, u16), u32> =
ProbeLedger::new(rate_limited_policy(), 8);
let t0 = Instant::now();
ledger.arm(HOST, (HOST, 80), 1, (), t0);
assert!(ledger.witness(&(HOST, 80), &1));
let mut seen = None;
for step in 1..20 {
let due = due_at(&mut ledger, t0 + Duration::from_secs(step));
for event in due {
match event {
Due::Retry { key, attempt } => ledger.rearm(HOST, key, attempt.into(), t0),
Due::Exhausted { witnessed, .. } => seen = Some(witnessed),
}
}
if seen.is_some() {
break;
}
}
assert_eq!(
seen,
Some(1),
"one send of several was watched leaving, and the caller is told so"
);
}
#[test]
fn the_silent_host_rule_can_be_turned_off() {
let base = rate_limited_policy();
assert!(base.silent_host.is_some(), "test premise");
let kept = base.configured(RetryConfig::default());
assert!(kept.silent_host.is_some());
let off = base.configured(RetryConfig {
dampen_silent_hosts: false,
..Default::default()
});
assert!(off.silent_host.is_none());
}
#[test]
fn a_thorough_scan_takes_no_shortcut_on_silent_hosts() {
let configured = rate_limited_policy().configured(effort(ScanEffort::Thorough));
assert!(configured.silent_host.is_none());
}
#[test]
fn a_scale_no_schedule_can_be_built_from_never_reaches_a_policy() {
for scale in [0.0, -1.0, f64::NAN, f64::INFINITY] {
assert_eq!(TimeoutScale::new(scale), None, "scale {scale}");
}
let base = policy();
let configured = base.configured(RetryConfig {
timeout_scale: TimeoutScale::new(2.0),
..Default::default()
});
assert_eq!(configured.initial_rto, base.initial_rto * 2);
}
use proptest::prelude::*;
proptest! {
#[test]
fn a_probe_never_exceeds_its_budget(
max_attempts in 1u8..6,
steps in 1usize..40,
) {
let policy = RetryPolicy::new(
max_attempts,
Duration::from_millis(10),
Duration::from_millis(1),
Duration::from_secs(1),
1.0,
0.0,
None,
);
let mut ledger = ledger(policy);
let t0 = Instant::now();
ledger.arm(HOST, (HOST, 80), 0, (), t0);
let mut sends = 1u8;
let mut exhausted = 0;
for step in 1..=steps {
let now = t0 + Duration::from_millis(10 * step as u64);
for event in due_at(&mut ledger, now) {
match event {
Due::Retry { key, attempt } => {
sends += 1;
prop_assert_eq!(attempt, sends);
ledger.arm(HOST, key, u32::from(attempt), (), now);
}
Due::Exhausted { .. } => exhausted += 1,
}
}
prop_assert!(sends <= max_attempts);
}
prop_assert!(exhausted <= 1, "a probe may only be retired once");
if exhausted == 1 {
prop_assert_eq!(sends, max_attempts);
prop_assert!(ledger.is_empty());
}
}
#[test]
fn resolving_at_any_point_is_final(resolve_after in 0u64..60) {
let policy = RetryPolicy::new(
4,
Duration::from_millis(10),
Duration::from_millis(1),
Duration::from_secs(1),
1.0,
0.0,
None,
);
let mut ledger = ledger(policy);
let t0 = Instant::now();
ledger.arm(HOST, (HOST, 80), 1, (), t0);
let resolve_at = t0 + Duration::from_millis(resolve_after);
let mut resolved = false;
let mut token = 1u32;
for step in 1..=8u64 {
let now = t0 + Duration::from_millis(10 * step);
if !resolved && resolve_at <= now {
resolved = ledger.resolve(&(HOST, 80), Some(token), resolve_at).is_some();
}
for event in due_at(&mut ledger, now) {
prop_assert!(!resolved, "a resolved probe produced {:?}", event);
if let Due::Retry { key, attempt } = event {
token = u32::from(attempt);
ledger.arm(HOST, key, token, (), now);
}
}
}
if resolved {
prop_assert!(ledger.resolve(&(HOST, 80), Some(token), resolve_at).is_none());
}
}
}
}