use std::collections::BTreeSet;
use std::ops::Range;
use serde::{Deserialize, Serialize};
use crate::model::ip::set::{IpSet, Positions};
use crate::model::target::{PlannedTarget, Target, TargetIndex};
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Cursor {
watermark: u64,
above: BTreeSet<u64>,
}
impl Cursor {
pub fn new() -> Self {
Self::default()
}
pub fn from_checkpoint(checkpoint: &Checkpoint) -> Self {
let mut cursor = Self {
watermark: checkpoint.watermark,
above: checkpoint
.settled_above
.iter()
.copied()
.filter(|position| *position >= checkpoint.watermark)
.collect(),
};
cursor.catch_up();
cursor
}
pub fn settle(&mut self, position: u64) {
if position < self.watermark {
return;
}
self.above.insert(position);
self.catch_up();
}
fn catch_up(&mut self) {
while self.above.remove(&self.watermark) {
self.watermark = self.watermark.saturating_add(1);
}
}
pub fn watermark(&self) -> u64 {
self.watermark
}
pub fn settled_above(&self) -> impl Iterator<Item = u64> + '_ {
self.above.iter().copied()
}
pub fn is_settled(&self, position: u64) -> bool {
position < self.watermark || self.above.contains(&position)
}
pub fn settled_count(&self) -> u64 {
self.watermark.saturating_add(self.above.len() as u64)
}
pub fn pending_count(&self) -> usize {
self.above.len()
}
pub fn checkpoint(&self) -> Checkpoint {
Checkpoint {
watermark: self.watermark,
settled_above: self.above.iter().copied().collect(),
}
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct Checkpoint {
pub watermark: u64,
#[serde(default)]
pub settled_above: Vec<u64>,
}
impl Checkpoint {
pub fn new(watermark: u64, settled_above: impl IntoIterator<Item = u64>) -> Self {
let mut settled_above: Vec<u64> = settled_above
.into_iter()
.filter(|position| *position >= watermark)
.collect();
settled_above.sort_unstable();
settled_above.dedup();
Self {
watermark,
settled_above,
}
}
pub fn is_settled(&self, position: u64) -> bool {
position < self.watermark || self.settled_above.binary_search(&position).is_ok()
}
pub fn remaining_addresses(&self, positions: &Positions) -> IpSet {
let mut remaining = IpSet::new();
for span in self.unsettled_spans(positions.total()) {
for range in positions.ranges_in(span) {
remaining.insert_range(range);
}
}
for range in positions.unnumbered() {
remaining.insert_range(*range);
}
remaining.canonicalize();
remaining
}
pub(crate) fn remaining_hosts(&self, index: &TargetIndex) -> IpSet {
let mut remaining = IpSet::new();
for span in self.unsettled_spans(index.total()) {
for range in index.addresses_in(span) {
remaining.insert_range(range);
}
}
for range in index.unnumbered_addresses() {
remaining.insert_range(*range);
}
remaining.canonicalize();
remaining
}
fn unsettled_spans(&self, total: u64) -> Vec<Range<u64>> {
let mut above = self.settled_above.clone();
above.sort_unstable();
let mut spans = Vec::with_capacity(above.len() + 1);
let mut from = self.watermark;
for settled in above {
if settled < from {
continue;
}
spans.push(from..settled.min(total));
from = settled.saturating_add(1);
}
spans.push(from..total);
spans.retain(|span| span.start < span.end);
spans
}
pub fn remaining<'a, I>(&'a self, targets: I) -> impl Iterator<Item = PlannedTarget> + 'a
where
I: IntoIterator<Item = Target> + 'a,
{
targets
.into_iter()
.enumerate()
.map(|(position, target)| PlannedTarget::new(position as u64, target))
.filter(move |planned| !self.is_settled(planned.position))
}
}
#[cfg(feature = "journal-format")]
mod persistence {
use std::fs;
use std::io::Write;
use std::path::Path;
use super::Checkpoint;
use crate::journal::file::create_staged;
use crate::journal::format::JournalError;
impl Checkpoint {
pub fn write_atomically(&self, path: &Path) -> Result<(), JournalError> {
let temporary = path.with_extension("tmp");
{
let mut file = create_staged(&temporary)?;
file.write_all(serde_json::to_string(self)?.as_bytes())?;
}
fs::rename(&temporary, path)?;
Ok(())
}
pub fn read(path: &Path) -> Result<Self, JournalError> {
let text = super::super::store::read_bounded(path, "a journal cursor")?;
let mut checkpoint: Self = serde_json::from_str(&text)?;
checkpoint.settled_above.sort_unstable();
checkpoint.settled_above.dedup();
Ok(checkpoint)
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::net::IpAddr;
fn addresses(written: &str) -> IpSet {
written.parse().expect("a valid address specification")
}
#[test]
fn a_resumed_sweep_asks_about_exactly_what_did_not_settle() {
let plan = addresses("192.0.2.1-192.0.2.10");
let positions = plan.positions();
let checkpoint = Checkpoint {
watermark: 3,
settled_above: vec![5, 8],
};
let remaining = checkpoint.remaining_addresses(&positions);
let found: Vec<IpAddr> = remaining.iter().collect();
let expected: Vec<IpAddr> = plan
.iter()
.enumerate()
.filter(|(position, _)| !checkpoint.is_settled(*position as u64))
.map(|(_, ip)| ip)
.collect();
assert_eq!(found, expected);
assert_eq!(
found.len(),
5,
"ten addresses, three settled below, two above"
);
}
#[test]
fn a_sweep_that_settled_nothing_resumes_over_the_whole_plan() {
let plan = addresses("192.0.2.1-192.0.2.10,2001:db8::1-2001:db8::4");
let remaining = Checkpoint::default().remaining_addresses(&plan.positions());
assert_eq!(remaining, plan);
}
#[test]
fn a_sweep_of_an_unnumberable_plan_resumes_over_all_of_it() {
let plan = addresses("192.0.2.0/30,2001:db8::/64");
let positions = plan.positions();
let checkpoint = Checkpoint {
watermark: 4,
settled_above: Vec::new(),
};
let remaining = checkpoint.remaining_addresses(&positions);
assert!(
!remaining.is_empty(),
"the /64 was never numbered and so was never settled"
);
assert_eq!(remaining.v4(), &[], "the numbered half did settle");
assert_eq!(remaining.v6(), plan.v6());
}
#[test]
fn a_finished_sweep_resumes_over_nothing() {
let plan = addresses("192.0.2.1-192.0.2.4");
let checkpoint = Checkpoint {
watermark: 4,
settled_above: Vec::new(),
};
assert!(checkpoint.remaining_addresses(&plan.positions()).is_empty());
}
#[test]
fn a_resumed_sweep_keeps_the_original_numbering() {
let plan = addresses("192.0.2.1-192.0.2.10");
let positions = plan.positions();
let checkpoint = Checkpoint {
watermark: 4,
settled_above: Vec::new(),
};
let remaining = checkpoint.remaining_addresses(&positions);
let first = remaining.iter().next().expect("something is left");
assert_eq!(
positions.find(first),
Some(4),
"the fifth address is still the fifth, not the first of what is left"
);
}
#[test]
fn an_unsorted_checkpoint_narrows_the_same_way() {
let plan = addresses("192.0.2.1-192.0.2.10");
let positions = plan.positions();
let sorted = Checkpoint {
watermark: 2,
settled_above: vec![4, 6, 9],
};
let shuffled = Checkpoint {
watermark: 2,
settled_above: vec![9, 4, 6],
};
assert_eq!(
sorted.remaining_addresses(&positions),
shuffled.remaining_addresses(&positions)
);
}
fn ports_plan() -> TargetMap {
let mut map = TargetMap::new();
for (range, ports) in [
("192.0.2.1-192.0.2.5", "22, 80, u:53"),
("198.51.100.7", "443"),
("203.0.113.0/30", "1-4, s:2905"),
("2001:db8::1-2001:db8::3", "80, u:161"),
] {
map.add_unit(TargetSet::new(
range.parse::<IpSet>().expect("a range"),
ports.parse::<PortSet>().expect("ports"),
));
}
map
}
fn hosts_of_remaining(checkpoint: &Checkpoint, map: &TargetMap) -> IpSet {
let mut hosts = IpSet::new();
for planned in checkpoint.remaining(map.iter()) {
hosts.insert(planned.ip());
}
hosts.canonicalize();
hosts
}
#[test]
fn a_resumed_port_scan_sweeps_only_the_hosts_with_a_target_left() {
let map = plan("192.0.2.1-192.0.2.3", "22, 80, 443");
let index = TargetIndex::of(&map);
let finished_second = Checkpoint::new(4, [4, 5]);
assert_eq!(
finished_second.remaining_hosts(&index),
addresses("192.0.2.3"),
"the first two settled every port between the watermark and the \
positions above it"
);
let one_port_short = Checkpoint::new(4, [5]);
assert_eq!(
one_port_short.remaining_hosts(&index),
addresses("192.0.2.2-192.0.2.3"),
"the second host's port at position 4 is still outstanding"
);
}
#[test]
fn a_finished_port_scan_resumes_with_no_host_to_sweep() {
let map = ports_plan();
let index = TargetIndex::of(&map);
let finished = Checkpoint::new(index.total(), []);
assert!(finished.remaining_hosts(&index).is_empty());
}
#[test]
fn a_port_scan_of_an_unnumberable_plan_sweeps_all_of_that_part() {
let mut map = plan("192.0.2.1", "22");
map.add_unit(TargetSet::new(
addresses("2001:db8::/64"),
"80".parse::<PortSet>().expect("ports"),
));
let index = TargetIndex::of(&map);
let remaining = Checkpoint::new(1, []).remaining_hosts(&index);
assert_eq!(remaining, addresses("2001:db8::/64"));
}
proptest::proptest! {
#[test]
fn the_hosts_swept_are_the_addresses_of_what_is_left(
watermark in 0u64..70,
above in proptest::collection::vec(0u64..72, 0..24),
) {
let map = ports_plan();
let index = TargetIndex::of(&map);
let checkpoint = Checkpoint::new(watermark, above);
proptest::prop_assert_eq!(
checkpoint.remaining_hosts(&index),
hosts_of_remaining(&checkpoint, &map)
);
}
}
use crate::model::ip::set::IpSet;
use crate::model::port::PortSet;
use crate::model::target::{TargetMap, TargetSet};
fn plan(range: &str, ports: &str) -> TargetMap {
let mut map = TargetMap::new();
map.add_unit(TargetSet::new(
range.parse::<IpSet>().expect("a range"),
ports.parse::<PortSet>().expect("ports"),
));
map
}
#[test]
fn settling_in_order_leaves_nothing_pending() {
let mut cursor = Cursor::new();
for position in 0..10 {
cursor.settle(position);
assert_eq!(cursor.watermark(), position + 1);
assert_eq!(cursor.pending_count(), 0, "nothing should be held");
}
}
#[test]
fn one_unsettled_position_stalls_the_watermark() {
let mut cursor = Cursor::new();
cursor.settle(0);
cursor.settle(1);
for position in 3..1_000 {
cursor.settle(position);
}
assert_eq!(cursor.watermark(), 2, "the gap at 2 must hold the line");
assert!(!cursor.is_settled(2));
assert_eq!(cursor.settled_count(), 999);
cursor.settle(2);
assert_eq!(cursor.watermark(), 1_000);
assert_eq!(cursor.pending_count(), 0);
}
#[test]
fn a_shuffled_walk_holds_what_has_settled_until_the_gaps_below_close() {
const PLAN: u64 = 4_096;
let order: Vec<u64> = crate::scanner::order::Permutation::new(7, PLAN)
.iter()
.collect();
let mut cursor = Cursor::new();
for position in &order[..order.len() / 2] {
cursor.settle(*position);
}
assert!(
cursor.pending_count() as u64 > PLAN * 2 / 5,
"halfway, {} of {} settled positions wait above a watermark of {}",
cursor.pending_count(),
PLAN / 2,
cursor.watermark()
);
for position in &order[order.len() / 2..] {
cursor.settle(*position);
}
assert_eq!(cursor.watermark(), PLAN);
assert_eq!(cursor.pending_count(), 0);
}
#[test]
fn the_watermark_is_independent_of_arrival_order() {
let forwards = {
let mut cursor = Cursor::new();
for position in 0..64 {
cursor.settle(position);
}
cursor
};
let backwards = {
let mut cursor = Cursor::new();
for position in (0..64).rev() {
cursor.settle(position);
}
cursor
};
let scattered = {
let mut cursor = Cursor::new();
for position in [7, 3, 63, 0, 1, 2, 4, 5, 6] {
cursor.settle(position);
}
for position in 8..63 {
cursor.settle(position);
}
cursor
};
assert_eq!(forwards.watermark(), 64);
assert_eq!(backwards.watermark(), 64);
assert_eq!(scattered.watermark(), 64);
assert_eq!(forwards, backwards);
assert_eq!(forwards, scattered);
}
#[test]
fn settling_the_same_position_twice_is_idempotent() {
let mut cursor = Cursor::new();
cursor.settle(0);
cursor.settle(0);
cursor.settle(0);
assert_eq!(cursor.watermark(), 1);
cursor.settle(5);
cursor.settle(5);
assert_eq!(cursor.pending_count(), 1);
assert_eq!(cursor.settled_count(), 2);
}
#[test]
fn a_cursor_survives_a_checkpoint() {
let mut cursor = Cursor::new();
for position in [0, 1, 2, 9, 11, 12] {
cursor.settle(position);
}
let restored = Cursor::from_checkpoint(&cursor.checkpoint());
assert_eq!(restored, cursor);
assert_eq!(restored.watermark(), 3);
assert!(restored.is_settled(9));
assert!(!restored.is_settled(3));
}
#[test]
fn remaining_yields_only_what_was_not_settled() {
let map = plan("192.0.2.1-192.0.2.4", "80,443");
let all: Vec<Target> = map.iter().collect();
assert_eq!(all.len(), 8, "four addresses on two ports");
let mut cursor = Cursor::new();
for position in [0, 1, 2, 5] {
cursor.settle(position);
}
let remaining: Vec<PlannedTarget> = cursor.checkpoint().remaining(map.iter()).collect();
assert_eq!(
remaining,
vec![
PlannedTarget::new(3, all[3]),
PlannedTarget::new(4, all[4]),
PlannedTarget::new(6, all[6]),
PlannedTarget::new(7, all[7]),
]
);
}
#[test]
fn the_empty_and_complete_cases_are_both_exact() {
let map = plan("192.0.2.1-192.0.2.4", "80,443");
let total = map.iter().count();
let untouched = Cursor::new().checkpoint();
assert_eq!(untouched.remaining(map.iter()).count(), total);
let mut finished = Cursor::new();
for position in 0..total as u64 {
finished.settle(position);
}
assert_eq!(finished.checkpoint().remaining(map.iter()).count(), 0);
assert_eq!(finished.watermark(), total as u64);
}
#[test]
fn positions_follow_the_plans_own_enumeration() {
let mut map = plan("192.0.2.1-192.0.2.2", "80,443");
map.add_unit(TargetSet::new(
"198.51.100.7".parse::<IpSet>().expect("a range"),
"22".parse::<PortSet>().expect("ports"),
));
let once: Vec<Target> = map.iter().collect();
let twice: Vec<Target> = map.iter().collect();
assert_eq!(once, twice, "the enumeration must be reproducible");
assert_eq!(once.len(), 5, "two units, four targets then one");
assert_eq!(
once[4].ip,
"198.51.100.7".parse::<std::net::IpAddr>().unwrap(),
"units are walked in the order they were added"
);
}
#[cfg(feature = "journal-format")]
#[test]
fn a_checkpoint_round_trips_through_a_file() {
let dir = std::env::temp_dir().join(format!(
"zond-cursor-{}-{:?}",
std::process::id(),
std::thread::current().id()
));
std::fs::create_dir_all(&dir).expect("scratch directory");
let path = dir.join("cursor.json");
let mut cursor = Cursor::new();
for position in [0, 1, 2, 9, 11, 12] {
cursor.settle(position);
}
cursor.checkpoint().write_atomically(&path).expect("writes");
assert_eq!(Checkpoint::read(&path).expect("reads"), cursor.checkpoint());
cursor.settle(3);
cursor
.checkpoint()
.write_atomically(&path)
.expect("rewrites");
let reread = Checkpoint::read(&path).expect("rereads");
assert_eq!(reread.watermark, 4);
assert!(
!dir.join("cursor.tmp").exists(),
"the temporary file must not survive the rename"
);
std::fs::remove_dir_all(&dir).ok();
}
#[cfg(feature = "journal-format")]
#[test]
fn a_checkpoint_with_an_unsorted_list_is_sorted_on_read() {
let dir = std::env::temp_dir().join(format!(
"zond-cursor-unsorted-{}-{:?}",
std::process::id(),
std::thread::current().id()
));
std::fs::create_dir_all(&dir).expect("scratch directory");
let path = dir.join("cursor.json");
std::fs::write(&path, r#"{"watermark":2,"settled_above":[9,4,7,4]}"#).expect("writes");
let checkpoint = Checkpoint::read(&path).expect("reads");
assert_eq!(
checkpoint.settled_above,
vec![4, 7, 9],
"sorted and deduped"
);
for position in [4, 7, 9] {
assert!(checkpoint.is_settled(position), "{position} is in the file");
}
assert!(!checkpoint.is_settled(3));
std::fs::remove_dir_all(&dir).ok();
}
#[test]
fn a_checkpoint_with_redundant_positions_normalises() {
let checkpoint = Checkpoint {
watermark: 5,
settled_above: vec![1, 2, 5, 6],
};
let cursor = Cursor::from_checkpoint(&checkpoint);
assert_eq!(cursor.watermark(), 7, "5 and 6 are contiguous with 5");
assert_eq!(cursor.pending_count(), 0);
assert_eq!(cursor.settled_count(), 7);
}
}