Skip to main content

zond_engine/journal/
cursor.rs

1// Copyright (c) 2026 Erik Lening (hollowpointer) and Contributors
2//
3// This file is part of Zond Engine, licensed under the GNU Affero General
4// Public License, version 3 or later. See the LICENSE file for details, or
5// <https://www.gnu.org/licenses/agpl-3.0.html>.
6//
7// SPDX-License-Identifier: AGPL-3.0-or-later
8
9//! # How far a scan got
10//!
11//! A position in the plan below which everything is settled, and the positions above it
12//! that settled out of order.
13//!
14//! ## A position needs nothing stored to name it
15//!
16//! [`TargetMap::iter`](crate::model::target::TargetMap::iter) walks its units in order and
17//! each unit's addresses against its ports, and a
18//! [`TargetSet`](crate::model::target::TargetSet) is canonical and immutable from
19//! construction. So the same plan yields the same targets in the same order on every run,
20//! and the nth target is a stable identity. The cursor holds integers, not addresses, and
21//! its size depends on how far out of order the scan settled, not on the scan's size.
22//!
23//! The dispatcher and this module must use one numbering. The order targets are asked in
24//! is separate: a scan given a seed walks a [`Permutation`] of the whole index space and
25//! numbers what comes out by where the plan holds it, through [`TargetIndex`]. `model`'s
26//! test `a_position_names_the_target_the_plans_own_walk_numbers_it` checks the index and
27//! this walk agree at every position.
28//!
29//! ## The watermark chases the settled set
30//!
31//! [`Cursor::settle`] records a position and then advances the watermark over every
32//! consecutive settled position above it. Anything settled out of order waits in
33//! [`above`](Cursor::settled_above) until the gap below it fills, so the set holds only what
34//! the watermark has not caught up to. How much that is depends on the walk order.
35//!
36//! Walked in plan order, it is bounded by how far the dispatcher runs ahead of the slowest
37//! outstanding probe. A single tarpitting host stalls the watermark and the set grows to
38//! the pipeline depth, then collapses when that host settles.
39//!
40//! Walked in a seeded [`Permutation`], as every scan the engine starts is, settled positions
41//! are scattered across the plan and a plan-order watermark stays near zero until nearly
42//! all are in. The set would be half the plan at the halfway mark.
43//!
44//! ## Two watermarks
45//!
46//! One counts in plan order, and one in the order the scan asks in: a [`Walk`](Walked)
47//! says that every position the permutation names before a given index is settled. A
48//! position is settled if either watermark has passed it or it waits in the set, and the
49//! set holds only what neither has reached.
50//!
51//! One of the two follows whichever order a phase settles in. A port scan's dispatcher walks
52//! the permutation, so the walk watermark keeps the set at pipeline size however large the
53//! plan. A link-layer sweep asks in address order, so the plan watermark does. A phase
54//! mixing the two also holds roughly the part of the plan the slower order has yet to reach.
55//!
56//! The walk (seed and length) is recorded beside the positions, so a checkpoint says on its
57//! own which targets it accounts for. Positions are still plan positions.
58//!
59//! An engine that predates the walk reads such a checkpoint as having settled only what the
60//! plan watermark and the set name, and asks again about what the walk covered. That costs
61//! probes and skips nothing, so no format version is spent on it.
62//!
63//! ## Only settled positions are recorded
64//!
65//! A position arrives only from [`Outcome`](super::settle::Outcome)'s settled variants. A
66//! target that was interrupted, never asked or never routed has no position, so the
67//! watermark stalls behind it and the next sitting asks again.
68
69use std::collections::BTreeSet;
70use std::ops::Range;
71
72use serde::{Deserialize, Serialize};
73
74use crate::model::ip::set::{IpSet, Positions};
75use crate::model::order::Permutation;
76use crate::model::target::{PlannedTarget, Target, TargetIndex};
77
78/// How far a scan has got, maintained as it runs.
79///
80/// Cheap to update. A snapshot holds what neither watermark has reached; see the
81/// module documentation.
82#[derive(Debug, Clone, Default, PartialEq, Eq)]
83pub struct Cursor {
84    watermark: u64,
85    above: BTreeSet<u64>,
86    walk: Option<Walked>,
87}
88
89impl Cursor {
90    /// A cursor over a plan with nothing settled yet, counted in plan order alone.
91    pub fn new() -> Self {
92        Self::default()
93    }
94
95    /// A cursor over a plan with nothing settled yet, that also counts along `order`,
96    /// the order the scan asks its targets in. Settled in that order, a plan of any size holds
97    /// about a pipeline's worth of positions.
98    pub fn walking(order: Permutation) -> Self {
99        Self::new().along(order)
100    }
101
102    /// Resumes from a checkpoint, along the walk it recorded if any.
103    pub fn from_checkpoint(checkpoint: &Checkpoint) -> Self {
104        let walk = checkpoint
105            .walked
106            .map(|walked| walked.clamped(checkpoint.watermark));
107        let mut cursor = Self {
108            watermark: checkpoint.watermark,
109            above: checkpoint
110                .settled_above
111                .iter()
112                .copied()
113                .filter(|position| *position >= checkpoint.watermark)
114                .filter(|position| !walk.is_some_and(|walk| walk.covers(*position)))
115                .collect(),
116            walk,
117        };
118        // A checkpoint written by a newer build, or edited by hand, may name positions
119        // already contiguous with a watermark; normalise so the invariants hold.
120        cursor.catch_up();
121        cursor
122    }
123
124    /// Counts along `order` as well, for a cursor not yet counting along any walk: one
125    /// resumed from a checkpoint written before the scan was walked, or by a sitting that was
126    /// not.
127    ///
128    /// A cursor already counting along a walk keeps it, since its positions were recorded
129    /// against that walk and a resume under the same manifest asks in that order anyway.
130    pub(crate) fn along(mut self, order: Permutation) -> Self {
131        if self.walk.is_none() {
132            self.walk = Some(Walked::start(order));
133            self.catch_up();
134        }
135        self
136    }
137
138    /// Records that the target at `position` is settled.
139    ///
140    /// Idempotent: settling a position already passed or recorded changes nothing. A
141    /// target can be reported twice, by a probe retired on its retry budget and then by a stop
142    /// path that does not know it already had a verdict.
143    pub fn settle(&mut self, position: u64) {
144        if self.is_settled(position) {
145            return;
146        }
147
148        self.above.insert(position);
149        self.catch_up();
150    }
151
152    /// Advances both watermarks over every settled position they can reach.
153    ///
154    /// Each can let the other go further: a position the walk passed may be the one the
155    /// plan watermark was waiting on, and vice versa. So they take turns until the walk stops
156    /// moving.
157    ///
158    /// Saturating, because positions may come from a cursor file this process did not write.
159    /// A planted `u64::MAX` would otherwise panic in debug or wrap to zero in release, silently
160    /// un-settling every finished target. Saturating wedges the watermark at the ceiling, which
161    /// errs towards re-probing.
162    fn catch_up(&mut self) {
163        let Self {
164            watermark,
165            above,
166            walk,
167        } = self;
168
169        loop {
170            loop {
171                if above.remove(watermark) {
172                    // Moves from the set to the watermark.
173                } else if let Some(walk) = walk.as_mut()
174                    && walk.covers(*watermark)
175                {
176                    // Counted as ahead when the walk passed it; now counted by the watermark.
177                    walk.ahead = walk.ahead.saturating_sub(1);
178                } else {
179                    break;
180                }
181                *watermark = watermark.saturating_add(1);
182            }
183
184            let Some(walk) = walk.as_mut() else { return };
185            let mut walked = false;
186            while let Some(position) = walk.order().at(walk.reached) {
187                if position < *watermark {
188                    // Already counted, below the plan watermark.
189                } else if above.remove(&position) {
190                    walk.ahead = walk.ahead.saturating_add(1);
191                } else {
192                    break;
193                }
194                walk.reached += 1;
195                walked = true;
196            }
197
198            if !walked {
199                return;
200            }
201        }
202    }
203
204    /// The position below which every target is settled, in plan order.
205    ///
206    /// A resume starts here, and skips the positions above it that
207    /// [`is_settled`](Self::is_settled) names.
208    pub fn watermark(&self) -> u64 {
209        self.watermark
210    }
211
212    /// The settled positions neither watermark has reached, ascending.
213    pub fn settled_above(&self) -> impl Iterator<Item = u64> + '_ {
214        self.above.iter().copied()
215    }
216
217    /// Whether the target at `position` may be skipped.
218    pub fn is_settled(&self, position: u64) -> bool {
219        position < self.watermark
220            || self.above.contains(&position)
221            || self.walk.is_some_and(|walk| walk.covers(position))
222    }
223
224    /// How many targets are settled in total.
225    ///
226    /// Saturating like the watermark's advance: a count that wrapped would report a
227    /// nearly finished scan as barely started.
228    pub fn settled_count(&self) -> u64 {
229        self.watermark
230            .saturating_add(self.walk.map_or(0, |walk| walk.ahead))
231            .saturating_add(self.above.len() as u64)
232    }
233
234    /// How many settled positions are waiting on a gap below them in both orders.
235    ///
236    /// The size of the out-of-order window, and so of a checkpoint. A number that keeps growing
237    /// means a target that never settles: a tarpit or a defect.
238    pub fn pending_count(&self) -> usize {
239        self.above.len()
240    }
241
242    /// A snapshot to write to disk.
243    pub fn checkpoint(&self) -> Checkpoint {
244        Checkpoint {
245            watermark: self.watermark,
246            settled_above: self.above.iter().copied().collect(),
247            walked: self.walk,
248        }
249    }
250}
251
252/// How far along the order a scan asks in everything is settled.
253///
254/// Every position [`Permutation::new(seed, len)`](Permutation::new) names before
255/// index `reached` is settled. Written down whole, so a checkpoint says on its own which
256/// positions it accounts for.
257#[non_exhaustive]
258#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
259pub struct Walked {
260    /// The key of the order walked.
261    pub seed: u64,
262    /// How many positions it rearranges: the plan's total.
263    pub len: u64,
264    /// How many of its positions, in the order it names them, are settled.
265    pub reached: u64,
266    /// How many of those are at or past the plan watermark.
267    ///
268    /// Lets a total be read without walking; the rest of what the walk reached is below the
269    /// watermark and already counted there. What a resume skips is decided by `reached`
270    /// alone.
271    pub ahead: u64,
272}
273
274impl Walked {
275    /// The start of a walk along `order`: nothing reached.
276    fn start(order: Permutation) -> Self {
277        Self {
278            seed: order.seed(),
279            len: order.len(),
280            reached: 0,
281            ahead: 0,
282        }
283    }
284
285    /// The order walked.
286    pub fn order(&self) -> Permutation {
287        Permutation::new(self.seed, self.len)
288    }
289
290    /// Whether the walk has passed `position`.
291    pub fn covers(&self, position: u64) -> bool {
292        self.order()
293            .index_of(position)
294            .is_some_and(|index| index < self.reached)
295    }
296
297    /// Clamped to what the numbers can mean, for values read from a file: no more
298    /// reached than the walk holds, and no more ahead than was reached or than the plan has past
299    /// `watermark`.
300    fn clamped(mut self, watermark: u64) -> Self {
301        self.reached = self.reached.min(self.len);
302        self.ahead = self
303            .ahead
304            .min(self.reached)
305            .min(self.len.saturating_sub(watermark));
306        self
307    }
308}
309
310/// A cursor as it is written down.
311///
312/// Two watermarks and the positions neither has reached. Settled in either order the
313/// scan counts in, that is a handful of positions however large the plan.
314#[non_exhaustive]
315#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
316pub struct Checkpoint {
317    /// The position below which everything is settled.
318    pub watermark: u64,
319    /// Settled positions at or above the watermark that the walk has not reached,
320    /// ascending.
321    ///
322    /// Ascending is an invariant: [`is_settled`](Self::is_settled) binary-searches it.
323    /// [`new`](Self::new) establishes it, and [`read`](Self::read) re-establishes it on anything
324    /// read from a file.
325    #[serde(default)]
326    pub settled_above: Vec<u64>,
327    /// How far along the order the scan asks in everything is settled, for a scan that
328    /// counted along one.
329    ///
330    /// Absent from a checkpoint of a scan that was not walked, or from an older engine. An
331    /// older engine reads a checkpoint carrying one as having settled less, which costs probes
332    /// and skips nothing.
333    #[serde(default, skip_serializing_if = "Option::is_none")]
334    pub walked: Option<Walked>,
335}
336
337impl Checkpoint {
338    /// A checkpoint over `watermark` and the settled positions above it.
339    ///
340    /// Sorts and deduplicates the list, the invariant [`is_settled`](Self::is_settled)
341    /// relies on. The fields are public, but this is the way that cannot build one wrong, and a
342    /// caller storing journals somewhere other than a directory should use it.
343    pub fn new(watermark: u64, settled_above: impl IntoIterator<Item = u64>) -> Self {
344        let mut settled_above: Vec<u64> = settled_above
345            .into_iter()
346            .filter(|position| *position >= watermark)
347            .collect();
348        settled_above.sort_unstable();
349        settled_above.dedup();
350
351        Self {
352            watermark,
353            settled_above,
354            walked: None,
355        }
356    }
357
358    /// Whether the target at `position` may be skipped.
359    ///
360    /// Binary-searched, so [`settled_above`](Self::settled_above) must be ascending;
361    /// [`new`](Self::new) guarantees that.
362    pub fn is_settled(&self, position: u64) -> bool {
363        position < self.watermark
364            || self.settled_above.binary_search(&position).is_ok()
365            || self.walked.is_some_and(|walked| walked.covers(position))
366    }
367
368    /// How many targets are settled in total.
369    ///
370    /// Read without walking: the watermark, what the walk counted past it, and the
371    /// positions neither reached. A listed position a watermark has passed is counted once, as
372    /// [`Cursor::from_checkpoint`] reads the same file.
373    pub fn settled_count(&self) -> u64 {
374        let walked = self.walked.map(|walked| walked.clamped(self.watermark));
375        let above = self
376            .settled_above
377            .iter()
378            .filter(|position| **position >= self.watermark)
379            .filter(|position| !walked.is_some_and(|walked| walked.covers(**position)))
380            .count();
381
382        self.watermark
383            .saturating_add(walked.map_or(0, |walked| walked.ahead))
384            .saturating_add(above as u64)
385    }
386
387    /// The addresses a resumed sweep still has to ask about.
388    ///
389    /// The sweep counterpart of [`remaining`](Self::remaining). Returns a set because a
390    /// [`HostScanner`](crate::scanner::strategy::HostScanner) owns its targets and its positions
391    /// come from the context; see
392    /// [`ScanContext::settle_address`](crate::scanner::session::ScanContext::settle_address),
393    /// which numbers an address against this same plan.
394    ///
395    /// Computed from the ranges: everything below the watermark is one span to drop, and the
396    /// positions settled out of order above it are taken out individually. Anything the plan
397    /// was too large to number comes back whole.
398    ///
399    /// `positions` must number the plan this checkpoint was written against; the manifest's
400    /// plan fingerprint refuses a mismatched resume before it gets here.
401    pub fn remaining_addresses(&self, positions: &Positions) -> IpSet {
402        let mut remaining = IpSet::new();
403
404        for span in self.unsettled_spans(positions.total()) {
405            for range in positions.ranges_in(span) {
406                remaining.insert_range(range);
407            }
408        }
409
410        // A range too large to number holds no position, so every sitting asks about it
411        // again.
412        for range in positions.unnumbered() {
413            remaining.insert_range(*range);
414        }
415
416        remaining.canonicalize();
417        remaining
418    }
419
420    /// The addresses a resumed port scan still has a target at.
421    ///
422    /// The port-plan counterpart of [`remaining_addresses`](Self::remaining_addresses),
423    /// for the host-level passes beside a port scan: the liveness sweep and the one that reads
424    /// hardware addresses and round trips. An address whose every target an earlier sitting
425    /// settled is not swept again.
426    ///
427    /// An address with any target outstanding comes back whole: whether the host is up is a
428    /// property of the network on the day, so this sitting establishes it for itself.
429    ///
430    /// Read host by host where that is cheaper, which for a partly finished scan it is by far;
431    /// see [`left_along`](Self::left_along).
432    ///
433    /// `index` must number the plan this checkpoint was written against, as for
434    /// [`remaining`](Self::remaining). Every address of a unit the index could not number comes
435    /// back, since none of its targets can have been settled.
436    pub(crate) fn remaining_hosts(&self, index: &TargetIndex) -> IpSet {
437        let mut remaining = IpSet::new();
438
439        for span in self.left_in(index) {
440            for range in index.addresses_in(span) {
441                remaining.insert_range(range);
442            }
443        }
444        for range in index.unnumbered_addresses() {
445            remaining.insert_range(*range);
446        }
447
448        remaining.canonicalize();
449        remaining
450    }
451
452    /// The stretches of `0..total` this checkpoint leaves unsettled, ascending and
453    /// non-empty, for a plan where each position is its own host, as in a sweep.
454    fn unsettled_spans(&self, total: u64) -> Vec<Range<u64>> {
455        self.left_in(&Alone(total))
456    }
457
458    /// Stretches of `runs`' positions, ascending and non-empty, holding every position
459    /// this checkpoint leaves unsettled and touching only hosts with one.
460    ///
461    /// Below the watermark everything is settled. Above it, a checkpoint counted in plan order
462    /// alone settled only the listed positions, so the stretches are the gaps between them. One
463    /// counted along a walk is read by [`left_along`](Self::left_along).
464    fn left_in(&self, runs: &impl HostRuns) -> Vec<Range<u64>> {
465        match self.walked {
466            Some(walked) => self.left_along(walked.clamped(self.watermark), runs),
467            None => self.spans_between(runs.total()),
468        }
469    }
470
471    /// The hosts of `runs` where a checkpoint counted along `walked` leaves a target,
472    /// as stretches of their whole runs of positions.
473    ///
474    /// What the walk has not reached is scattered across the plan. There are two ways to find
475    /// it, each cheap where the other is expensive.
476    ///
477    /// **Host by host.** Each host past the watermark is asked, one position at a time, whether
478    /// that position is settled, and the first that is not answers for the host. A host with
479    /// `u` positions left is answered after about `1 / u` of them, so with half the plan left it
480    /// costs about two questions a host and holds nothing. The cost grows as the plan empties:
481    /// a finished host is asked every position.
482    ///
483    /// **Along the walk's tail.** The positions not yet reached are exactly those the walk names
484    /// from `reached` on, so reading them and marking each one's host costs the tail length and
485    /// a bit a host. Cheap late in a scan and expensive early: a `/8` on a thousand ports
486    /// resumed half way has eight billion tail positions and sixteen million hosts.
487    ///
488    /// With `h` hosts, `n` positions past the watermark and `t` in the tail, the first costs
489    /// about `h * min(n / h, n / t)` and the second `t`, so the tail is cheaper exactly when
490    /// `t * t < h * n`. At the crossing either costs `h` times the square root of a host's
491    /// ports. Past [`MARKED_AT_MOST`] hosts no bitmap is built and the plan is read host by
492    /// host.
493    fn left_along(&self, walked: Walked, runs: &impl HostRuns) -> Vec<Range<u64>> {
494        let total = runs.total();
495        if self.watermark >= total {
496            return Vec::new();
497        }
498
499        let first = runs.host_of(self.watermark);
500        let hosts = runs.hosts() - first;
501        let past = total - self.watermark;
502        let tail = walked.len - walked.reached;
503
504        let order = walked.order();
505        let listed = |position: u64| self.settled_above.binary_search(&position).is_ok();
506
507        if reads_the_tail(tail, hosts, past) {
508            let reached = order
509                .iter_from(walked.reached)
510                .filter(|position| *position >= self.watermark && *position < total)
511                .filter(|position| !listed(*position));
512            // A plan longer than the walk, which only a damaged file describes: the walk
513            // names nothing past its end, so only the list can have settled any of it.
514            let unwalked = self
515                .gaps_from(walked.len.max(self.watermark), total)
516                .into_iter()
517                .flatten();
518            return marked(runs, first, hosts, reached.chain(unwalked));
519        }
520
521        let unsettled = |position: u64| {
522            position >= self.watermark
523                && !listed(position)
524                && !order
525                    .index_of(position)
526                    .is_some_and(|index| index < walked.reached)
527        };
528        host_by_host(runs, first..runs.hosts(), unsettled)
529    }
530
531    /// The unsettled stretches of a checkpoint counted in plan order alone: the gaps
532    /// between the listed positions.
533    fn spans_between(&self, total: u64) -> Vec<Range<u64>> {
534        self.gaps_from(self.watermark, total)
535    }
536
537    /// The gaps between the positions the list names, from `from` to `total`.
538    fn gaps_from(&self, from: u64, total: u64) -> Vec<Range<u64>> {
539        // A checkpoint from disk is only as ordered as the file was. Sorting a copy is
540        // linear on an already sorted list.
541        let mut above = self.settled_above.clone();
542        above.sort_unstable();
543
544        let mut spans = Vec::with_capacity(above.len() + 1);
545        let mut from = from;
546        for settled in above {
547            if settled < from {
548                continue;
549            }
550            spans.push(from..settled.min(total));
551            from = settled.saturating_add(1);
552        }
553        spans.push(from..total);
554
555        spans.retain(|span| span.start < span.end);
556        spans
557    }
558
559    /// The targets a resumed scan still has to ask about, each carrying its
560    /// position in the original plan.
561    ///
562    /// Takes the plan's enumeration,
563    /// [`TargetMap::iter`](crate::model::target::TargetMap::iter), the walk the first sitting
564    /// was numbered by, and yields only what this checkpoint does not account for.
565    ///
566    /// Yields [`PlannedTarget`] so the original numbering survives the filtering: numbering the
567    /// subset afresh would give position 0 to whatever is left, and the two sittings' cursors
568    /// would count different things.
569    ///
570    /// The plan must be the one this checkpoint was written against. A changed port list,
571    /// exclusion policy or privilege level moves what each position refers to. Nothing here
572    /// detects that; the manifest's plan fingerprint refuses the resume first.
573    pub fn remaining<'a, I>(&'a self, targets: I) -> impl Iterator<Item = PlannedTarget> + 'a
574    where
575        I: IntoIterator<Item = Target> + 'a,
576    {
577        targets
578            .into_iter()
579            .enumerate()
580            .map(|(position, target)| PlannedTarget::new(position as u64, target))
581            .filter(move |planned| !self.is_settled(planned.position))
582    }
583}
584
585/// The most hosts [`Checkpoint::left_along`] marks in a bitmap, a bit each: 128
586/// MiB, every address of a quarter of IPv4.
587///
588/// A plan with more is read host by host. Only a plan with an IPv6 range comes near it.
589const MARKED_AT_MOST: u64 = 1 << 30;
590
591/// Whether [`Checkpoint::left_along`] reads the walk's tail of `tail` positions
592/// instead of asking `hosts` hosts holding `past` positions one by one: where the tail is
593/// cheaper and its bitmap is within [`MARKED_AT_MOST`].
594fn reads_the_tail(tail: u64, hosts: u64, past: u64) -> bool {
595    let tail = u128::from(tail);
596    tail * tail < u128::from(hosts) * u128::from(past) && hosts <= MARKED_AT_MOST
597}
598
599/// A numbering of targets seen host by host: each host's targets hold a contiguous
600/// run of positions, and the runs ascend.
601///
602/// In a port plan the hosts are addresses, each with a run of its ports, since the port
603/// index runs fastest; see [`TargetIndex`]. In a sweep each address is a run of one.
604trait HostRuns {
605    /// How many positions are numbered.
606    fn total(&self) -> u64;
607    /// How many hosts hold them.
608    fn hosts(&self) -> u64;
609    /// The positions of host `host`, which is below [`hosts`](Self::hosts).
610    fn run(&self, host: u64) -> Range<u64>;
611    /// The host whose run holds `position`, which is below [`total`](Self::total).
612    fn host_of(&self, position: u64) -> u64;
613}
614
615impl HostRuns for TargetIndex {
616    fn total(&self) -> u64 {
617        TargetIndex::total(self)
618    }
619
620    fn hosts(&self) -> u64 {
621        TargetIndex::hosts(self)
622    }
623
624    fn run(&self, host: u64) -> Range<u64> {
625        self.host_run(host)
626    }
627
628    fn host_of(&self, position: u64) -> u64 {
629        TargetIndex::host_of(self, position)
630    }
631}
632
633/// `0..n` with every position a host of its own, as a sweep numbers addresses.
634struct Alone(u64);
635
636impl HostRuns for Alone {
637    fn total(&self) -> u64 {
638        self.0
639    }
640
641    fn hosts(&self) -> u64 {
642        self.0
643    }
644
645    fn run(&self, host: u64) -> Range<u64> {
646        host..host + 1
647    }
648
649    fn host_of(&self, position: u64) -> u64 {
650        position
651    }
652}
653
654/// The runs of the hosts in `hosts` with a position `unsettled` answers for, merged
655/// where they meet. Each host is asked one position at a time, in plan order; see
656/// [`Checkpoint::left_along`].
657fn host_by_host(
658    runs: &impl HostRuns,
659    hosts: Range<u64>,
660    mut unsettled: impl FnMut(u64) -> bool,
661) -> Vec<Range<u64>> {
662    let mut spans = Vec::new();
663    for host in hosts {
664        let run = runs.run(host);
665        if run.clone().any(&mut unsettled) {
666            extend(&mut spans, run);
667        }
668    }
669    spans
670}
671
672/// The runs of the hosts holding any of `positions`, merged where they meet, for
673/// `hosts` hosts numbered from `first`. Marked in a bitmap in any order and read back in
674/// plan order; see [`Checkpoint::left_along`].
675fn marked(
676    runs: &impl HostRuns,
677    first: u64,
678    hosts: u64,
679    positions: impl Iterator<Item = u64>,
680) -> Vec<Range<u64>> {
681    // Within `MARKED_AT_MOST`, so the words fit in memory and their count in a
682    // `usize`.
683    let mut bits = vec![0u64; hosts.div_ceil(64) as usize];
684    for position in positions {
685        let host = runs.host_of(position) - first;
686        bits[(host / 64) as usize] |= 1 << (host % 64);
687    }
688
689    let mut spans = Vec::new();
690    for (at, word) in bits.iter().enumerate() {
691        let mut word = *word;
692        while word != 0 {
693            let host = first + at as u64 * 64 + u64::from(word.trailing_zeros());
694            extend(&mut spans, runs.run(host));
695            word &= word - 1;
696        }
697    }
698    spans
699}
700
701/// Appends `run` to `spans`, joining the last one where the two meet.
702fn extend(spans: &mut Vec<Range<u64>>, run: Range<u64>) {
703    match spans.last_mut() {
704        Some(span) if span.end == run.start => span.end = run.end,
705        _ => spans.push(run),
706    }
707}
708
709#[cfg(feature = "journal-format")]
710mod persistence {
711    use std::io::Write;
712    use std::path::Path;
713
714    use super::Checkpoint;
715    use crate::journal::file::replace;
716    use crate::journal::format::JournalError;
717
718    impl Checkpoint {
719        /// Writes the checkpoint so that a process killed mid-write leaves the previous one
720        /// intact.
721        ///
722        /// Writes a sibling temporary file and renames it over the destination, which is atomic on
723        /// every filesystem this engine runs on, so a reader sees one whole checkpoint or the one
724        /// before. No `fsync`: `^C`, a dropped session and an OOM kill are process deaths, and the
725        /// page cache outlives the process. See [`journal`](crate::journal).
726        pub fn write_atomically(&self, path: &Path) -> Result<(), JournalError> {
727            let text = serde_json::to_string(self).map_err(JournalError::json)?;
728            replace(path, &path.with_extension("tmp"), |mut file| {
729                file.write_all(text.as_bytes())
730            })?;
731            Ok(())
732        }
733
734        /// Reads a checkpoint back.
735        ///
736        /// The `settled_above` list is sorted on read, since
737        /// [`is_settled`](Checkpoint::is_settled) binary-searches it and an unsorted list would
738        /// miss a position that is present and re-probe a settled target.
739        pub fn read(path: &Path) -> Result<Self, JournalError> {
740            let text = super::super::store::read_bounded(path, "a journal cursor")?;
741            let mut checkpoint: Self = serde_json::from_str(&text).map_err(JournalError::json)?;
742            checkpoint.settled_above.sort_unstable();
743            checkpoint.settled_above.dedup();
744            Ok(checkpoint)
745        }
746    }
747}
748
749// ╔════════════════════════════════════════════╗
750// ║ ████████╗███████╗███████╗████████╗███████╗ ║
751// ║ ╚══██╔══╝██╔════╝██╔════╝╚══██╔══╝██╔════╝ ║
752// ║    ██║   █████╗  ███████╗   ██║   ███████╗ ║
753// ║    ██║   ██╔══╝  ╚════██║   ██║   ╚════██║ ║
754// ║    ██║   ███████╗███████║   ██║   ███████║ ║
755// ║    ╚═╝   ╚══════╝╚══════╝   ╚═╝   ╚══════╝ ║
756// ╚════════════════════════════════════════════╝
757
758#[cfg(test)]
759mod tests {
760    use super::*;
761
762    // ─── Resuming a sweep ────────────────────────────────────────────────────
763
764    use std::net::IpAddr;
765
766    fn addresses(written: &str) -> IpSet {
767        written.parse().expect("a valid address specification")
768    }
769
770    /// A resumed sweep asks about exactly what the first sitting did not settle. One
771    /// address too few is a target silently skipped.
772    #[test]
773    fn a_resumed_sweep_asks_about_exactly_what_did_not_settle() {
774        let plan = addresses("192.0.2.1-192.0.2.10");
775        let positions = plan.positions();
776
777        let checkpoint = Checkpoint {
778            watermark: 3,
779            settled_above: vec![5, 8],
780            walked: None,
781        };
782
783        let remaining = checkpoint.remaining_addresses(&positions);
784        let found: Vec<IpAddr> = remaining.iter().collect();
785        let expected: Vec<IpAddr> = plan
786            .iter()
787            .enumerate()
788            .filter(|(position, _)| !checkpoint.is_settled(*position as u64))
789            .map(|(_, ip)| ip)
790            .collect();
791
792        assert_eq!(found, expected);
793        assert_eq!(
794            found.len(),
795            5,
796            "ten addresses, three settled below, two above"
797        );
798    }
799
800    /// A sweep that settled nothing comes back whole.
801    #[test]
802    fn a_sweep_that_settled_nothing_resumes_over_the_whole_plan() {
803        let plan = addresses("192.0.2.1-192.0.2.10,2001:db8::1-2001:db8::4");
804        let remaining = Checkpoint::default().remaining_addresses(&plan.positions());
805
806        assert_eq!(remaining, plan);
807    }
808
809    /// A range too large to number comes back whole, however far the numbered part got,
810    /// so a resumed IPv6 sweep does not ask about nothing and report that it finished.
811    #[test]
812    fn a_sweep_of_an_unnumberable_plan_resumes_over_all_of_it() {
813        let plan = addresses("192.0.2.0/30,2001:db8::/64");
814        let positions = plan.positions();
815
816        let checkpoint = Checkpoint {
817            watermark: 4,
818            settled_above: Vec::new(),
819            walked: None,
820        };
821        let remaining = checkpoint.remaining_addresses(&positions);
822
823        assert!(
824            !remaining.is_empty(),
825            "the /64 was never numbered and so was never settled"
826        );
827        assert_eq!(remaining.v4(), &[], "the numbered half did settle");
828        assert_eq!(remaining.v6(), plan.v6());
829    }
830
831    /// A sweep that settled everything has nothing left to ask.
832    #[test]
833    fn a_finished_sweep_resumes_over_nothing() {
834        let plan = addresses("192.0.2.1-192.0.2.4");
835        let checkpoint = Checkpoint {
836            watermark: 4,
837            settled_above: Vec::new(),
838            walked: None,
839        };
840
841        assert!(checkpoint.remaining_addresses(&plan.positions()).is_empty());
842    }
843
844    /// An address in the narrowed set numbers the same as it did in the first sitting.
845    #[test]
846    fn a_resumed_sweep_keeps_the_original_numbering() {
847        let plan = addresses("192.0.2.1-192.0.2.10");
848        let positions = plan.positions();
849        let checkpoint = Checkpoint {
850            watermark: 4,
851            settled_above: Vec::new(),
852            walked: None,
853        };
854
855        let remaining = checkpoint.remaining_addresses(&positions);
856        let first = remaining.iter().next().expect("something is left");
857
858        assert_eq!(
859            positions.find(first),
860            Some(4),
861            "the fifth address is still the fifth, not the first of what is left"
862        );
863    }
864
865    /// A checkpoint read from a file is only as ordered as the file was.
866    #[test]
867    fn an_unsorted_checkpoint_narrows_the_same_way() {
868        let plan = addresses("192.0.2.1-192.0.2.10");
869        let positions = plan.positions();
870
871        let sorted = Checkpoint {
872            watermark: 2,
873            settled_above: vec![4, 6, 9],
874            walked: None,
875        };
876        let shuffled = Checkpoint {
877            watermark: 2,
878            settled_above: vec![9, 4, 6],
879            walked: None,
880        };
881
882        assert_eq!(
883            sorted.remaining_addresses(&positions),
884            shuffled.remaining_addresses(&positions)
885        );
886    }
887
888    // ─── Resuming a port scan's host passes ──────────────────────────────────
889
890    /// Several units, both families, and port counts that divide nothing, so an
891    /// address's ports straddle every kind of boundary a span can end on.
892    fn ports_plan() -> TargetMap {
893        let mut map = TargetMap::new();
894        for (range, ports) in [
895            ("192.0.2.1-192.0.2.5", "22, 80, u:53"),
896            ("198.51.100.7", "443"),
897            ("203.0.113.0/30", "1-4, s:2905"),
898            ("2001:db8::1-2001:db8::3", "80, u:161"),
899        ] {
900            map.add_unit(TargetSet::new(
901                range.parse::<IpSet>().expect("a range"),
902                ports.parse::<PortSet>().expect("ports"),
903            ));
904        }
905        map
906    }
907
908    /// The addresses of what [`Checkpoint::remaining`] still yields, which
909    /// `remaining_hosts` must agree with.
910    fn hosts_of_remaining(checkpoint: &Checkpoint, map: &TargetMap) -> IpSet {
911        let mut hosts = IpSet::new();
912        for planned in checkpoint.remaining(map.iter()) {
913            hosts.insert(planned.ip());
914        }
915        hosts.canonicalize();
916        hosts
917    }
918
919    /// An address with a target left is swept, and one whose every target settled is
920    /// not, however the settling fell across its ports.
921    #[test]
922    fn a_resumed_port_scan_sweeps_only_the_hosts_with_a_target_left() {
923        // Three ports each: 192.0.2.1 is positions 0-2, .2 is 3-5, .3 is 6-8.
924        let map = plan("192.0.2.1-192.0.2.3", "22, 80, 443");
925        let index = TargetIndex::of(&map);
926
927        let finished_second = Checkpoint::new(4, [4, 5]);
928        assert_eq!(
929            finished_second.remaining_hosts(&index),
930            addresses("192.0.2.3"),
931            "the first two settled every port between the watermark and the \
932             positions above it"
933        );
934
935        let one_port_short = Checkpoint::new(4, [5]);
936        assert_eq!(
937            one_port_short.remaining_hosts(&index),
938            addresses("192.0.2.2-192.0.2.3"),
939            "the second host's port at position 4 is still outstanding"
940        );
941    }
942
943    /// A walked checkpoint over `len` positions that reached `reached` of them, with
944    /// `watermark` and `above` settled in plan order.
945    fn walked(seed: u64, len: u64, reached: u64, watermark: u64, above: Vec<u64>) -> Checkpoint {
946        Checkpoint {
947            walked: Some(Walked {
948                seed,
949                len,
950                reached,
951                ahead: 0,
952            }),
953            ..Checkpoint::new(watermark, above)
954        }
955    }
956
957    /// A scan resumed part way is read host by host, and one nearly done along its tail.
958    /// Half way through a `/8` on a thousand ports the tail is eight billion positions, while
959    /// host by host it is about two questions for each of sixteen million hosts. Near the end
960    /// the tail is the short read. A sweep, whose hosts are its positions, reads whichever part
961    /// is left.
962    #[test]
963    fn a_resume_reads_whichever_of_the_hosts_and_the_tail_is_shorter() {
964        let hosts: u64 = 1 << 24;
965        let plan = hosts * 1_000;
966
967        assert!(!reads_the_tail(plan / 2, hosts, plan), "half way");
968        assert!(!reads_the_tail(plan / 16, hosts, plan), "a sixteenth left");
969        assert!(
970            reads_the_tail(plan / 64, hosts, plan),
971            "a sixty-fourth left"
972        );
973        assert!(reads_the_tail(plan / 10_000, hosts, plan), "nearly done");
974
975        assert!(reads_the_tail(hosts / 2, hosts, hosts), "a sweep half way");
976        assert!(
977            !reads_the_tail(1, MARKED_AT_MOST + 1, MARKED_AT_MOST + 1),
978            "more hosts than a bitmap is kept for"
979        );
980    }
981
982    /// Half way through a `/16` on 1,024 ports every host still has a target left, and
983    /// the answer comes back without reading the tail's 33 million positions.
984    #[test]
985    fn a_wide_port_scan_resumed_half_way_sweeps_every_host() {
986        let map = plan("198.51.0.0/16", "1-1024");
987        let index = TargetIndex::of(&map);
988        let len = index.total();
989
990        let remaining = walked(0x5EED, len, len / 2, 0, Vec::new()).remaining_hosts(&index);
991
992        assert_eq!(remaining, addresses("198.51.0.0/16"));
993    }
994
995    /// A port scan whose first sitting settled everything has no host left to sweep.
996    #[test]
997    fn a_finished_port_scan_resumes_with_no_host_to_sweep() {
998        let map = ports_plan();
999        let index = TargetIndex::of(&map);
1000        let finished = Checkpoint::new(index.total(), []);
1001
1002        assert!(finished.remaining_hosts(&index).is_empty());
1003    }
1004
1005    /// A unit the numbering cannot reach is swept whole, since none of it can have been
1006    /// settled.
1007    #[test]
1008    fn a_port_scan_of_an_unnumberable_plan_sweeps_all_of_that_part() {
1009        let mut map = plan("192.0.2.1", "22");
1010        map.add_unit(TargetSet::new(
1011            addresses("2001:db8::/64"),
1012            "80".parse::<PortSet>().expect("ports"),
1013        ));
1014        let index = TargetIndex::of(&map);
1015
1016        let remaining = Checkpoint::new(1, []).remaining_hosts(&index);
1017
1018        assert_eq!(remaining, addresses("2001:db8::/64"));
1019    }
1020
1021    proptest::proptest! {
1022        /// Whatever a walk reached, the hosts a resumed sitting sweeps are exactly the
1023        /// addresses of the targets it still probes, along the tail late in the walk and host by
1024        /// host early. A walk shorter than the plan (a damaged file) leaves the rest to the list.
1025        #[test]
1026        fn the_hosts_swept_after_a_walk_are_the_addresses_of_what_is_left(
1027            seed in proptest::prelude::any::<u64>(),
1028            reached in 0u64..=72,
1029            short in 0u64..4,
1030            watermark in 0u64..70,
1031            above in proptest::collection::vec(0u64..72, 0..24),
1032        ) {
1033            let map = ports_plan();
1034            let index = TargetIndex::of(&map);
1035            let len = index.total() - short;
1036            let checkpoint = walked(seed, len, reached.min(len), watermark, above);
1037
1038            proptest::prop_assert_eq!(
1039                checkpoint.remaining_hosts(&index),
1040                hosts_of_remaining(&checkpoint, &map)
1041            );
1042        }
1043
1044        /// Whatever an earlier sitting settled, the hosts a resumed sitting sweeps are
1045        /// exactly the addresses of the targets it still probes. Positions past the plan are
1046        /// included, as a checkpoint read from a file can hold them.
1047        #[test]
1048        fn the_hosts_swept_are_the_addresses_of_what_is_left(
1049            watermark in 0u64..70,
1050            above in proptest::collection::vec(0u64..72, 0..24),
1051        ) {
1052            let map = ports_plan();
1053            let index = TargetIndex::of(&map);
1054            let checkpoint = Checkpoint::new(watermark, above);
1055
1056            proptest::prop_assert_eq!(
1057                checkpoint.remaining_hosts(&index),
1058                hosts_of_remaining(&checkpoint, &map)
1059            );
1060        }
1061    }
1062
1063    use crate::model::ip::set::IpSet;
1064    use crate::model::port::PortSet;
1065    use crate::model::target::{TargetMap, TargetSet};
1066
1067    fn plan(range: &str, ports: &str) -> TargetMap {
1068        let mut map = TargetMap::new();
1069        map.add_unit(TargetSet::new(
1070            range.parse::<IpSet>().expect("a range"),
1071            ports.parse::<PortSet>().expect("ports"),
1072        ));
1073        map
1074    }
1075
1076    /// Settling in order: the watermark follows and nothing is held.
1077    #[test]
1078    fn settling_in_order_leaves_nothing_pending() {
1079        let mut cursor = Cursor::new();
1080
1081        for position in 0..10 {
1082            cursor.settle(position);
1083            assert_eq!(cursor.watermark(), position + 1);
1084            assert_eq!(cursor.pending_count(), 0, "nothing should be held");
1085        }
1086    }
1087
1088    /// One unsettled position stalls the watermark however much settles above it.
1089    /// Otherwise a resumed scan would skip a target nobody probed.
1090    #[test]
1091    fn one_unsettled_position_stalls_the_watermark() {
1092        let mut cursor = Cursor::new();
1093
1094        cursor.settle(0);
1095        cursor.settle(1);
1096        // 2 is still outstanding: a tarpit, or a probe mid-retry.
1097        for position in 3..1_000 {
1098            cursor.settle(position);
1099        }
1100
1101        assert_eq!(cursor.watermark(), 2, "the gap at 2 must hold the line");
1102        assert!(!cursor.is_settled(2));
1103        assert_eq!(cursor.settled_count(), 999);
1104
1105        // It collapses when the gap fills.
1106        cursor.settle(2);
1107        assert_eq!(cursor.watermark(), 1_000);
1108        assert_eq!(cursor.pending_count(), 0);
1109    }
1110
1111    /// Counted along the walk, a shuffled scan holds only what is in flight; counted in
1112    /// plan order alone, the set is most of what has settled. Both halves are asserted, so the
1113    /// order is shown to be the reason.
1114    #[test]
1115    fn a_shuffled_walk_holds_only_what_is_in_flight_when_counted_along_it() {
1116        const PLAN: u64 = 4_096;
1117        let order = Permutation::new(7, PLAN);
1118        let asked: Vec<u64> = order.iter().collect();
1119
1120        let mut in_plan_order = Cursor::new();
1121        let mut along = Cursor::walking(order);
1122        for window in asked.chunks(16) {
1123            // Answers come back out of order within what is in flight.
1124            for position in window.iter().rev() {
1125                in_plan_order.settle(*position);
1126                along.settle(*position);
1127            }
1128            assert!(along.pending_count() < 16, "{}", along.pending_count());
1129            if along.settled_count() == PLAN / 2 {
1130                assert!(
1131                    in_plan_order.pending_count() as u64 > PLAN * 2 / 5,
1132                    "halfway, {} settled positions wait above a watermark of {}",
1133                    in_plan_order.pending_count(),
1134                    in_plan_order.watermark()
1135                );
1136            }
1137        }
1138
1139        for cursor in [&in_plan_order, &along] {
1140            assert_eq!(cursor.settled_count(), PLAN);
1141            assert_eq!(cursor.pending_count(), 0);
1142            assert!((0..PLAN).all(|position| cursor.is_settled(position)));
1143        }
1144    }
1145
1146    /// A cursor counting along a walk still follows a phase that settles in plan order.
1147    #[test]
1148    fn a_walked_cursor_settled_in_plan_order_holds_nothing_either() {
1149        let mut cursor = Cursor::walking(Permutation::new(7, 1_000));
1150        for position in 0..1_000 {
1151            cursor.settle(position);
1152            assert_eq!(cursor.pending_count(), 0, "at {position}");
1153        }
1154        assert_eq!(cursor.settled_count(), 1_000);
1155        assert_eq!(cursor.watermark(), 1_000);
1156    }
1157
1158    proptest::proptest! {
1159        /// Whatever order positions settle in, the two watermarks and the set between them
1160        /// name exactly what settled, count it once, and say the same after a round trip through a
1161        /// checkpoint. A position named that did not settle is a target a resume skips unasked.
1162        #[test]
1163        fn two_watermarks_name_exactly_what_settled(
1164            seed in proptest::prelude::any::<u64>(),
1165            len in 1u64..300,
1166            settled in proptest::collection::vec(0u64..320, 0..400),
1167            walked_first in 0usize..300,
1168        ) {
1169            let order = Permutation::new(seed, len);
1170            let mut cursor = Cursor::walking(order);
1171            // Some of the walk in its own order, then the rest in any order, as a phase mixing
1172            // a dispatcher and a sweep would.
1173            let mut expected = BTreeSet::new();
1174            for position in order.iter().take(walked_first) {
1175                cursor.settle(position);
1176                expected.insert(position);
1177            }
1178            for position in settled {
1179                cursor.settle(position);
1180                expected.insert(position);
1181            }
1182
1183            let checkpoint = cursor.checkpoint();
1184            let restored = Cursor::from_checkpoint(&checkpoint);
1185            for position in 0..330 {
1186                let want = expected.contains(&position);
1187                proptest::prop_assert_eq!(cursor.is_settled(position), want, "cursor, {}", position);
1188                proptest::prop_assert_eq!(checkpoint.is_settled(position), want, "checkpoint, {}", position);
1189                proptest::prop_assert_eq!(restored.is_settled(position), want, "restored, {}", position);
1190            }
1191            proptest::prop_assert_eq!(cursor.settled_count(), expected.len() as u64);
1192            proptest::prop_assert_eq!(checkpoint.settled_count(), expected.len() as u64);
1193            proptest::prop_assert_eq!(restored.settled_count(), expected.len() as u64);
1194
1195            // A resume asks about exactly the rest.
1196            let total = len + 10;
1197            let spans: Vec<u64> = checkpoint
1198                .unsettled_spans(total)
1199                .into_iter()
1200                .flatten()
1201                .collect();
1202            let rest: Vec<u64> = (0..total).filter(|p| !expected.contains(p)).collect();
1203            proptest::prop_assert_eq!(spans, rest);
1204        }
1205    }
1206
1207    /// A walk attached to a cursor resumed from a walkless checkpoint keeps everything
1208    /// that checkpoint settled.
1209    #[test]
1210    fn a_walk_joins_a_cursor_resumed_without_one() {
1211        let order = Permutation::new(11, 64);
1212        let earlier: Vec<u64> = order.iter().take(40).collect();
1213        let checkpoint = Checkpoint::new(0, earlier.iter().copied());
1214
1215        let cursor = Cursor::from_checkpoint(&checkpoint).along(order);
1216
1217        assert_eq!(cursor.pending_count(), 0, "the walk reached all of it");
1218        assert_eq!(cursor.settled_count(), 40);
1219        assert!(earlier.iter().all(|position| cursor.is_settled(*position)));
1220    }
1221
1222    /// An engine that predates the walk reads a checkpoint carrying one as having
1223    /// settled less than it did, never more.
1224    #[cfg(feature = "journal-format")]
1225    #[test]
1226    fn an_older_reader_takes_a_walked_checkpoint_for_less_than_it_settled() {
1227        #[derive(Deserialize)]
1228        struct Older {
1229            watermark: u64,
1230            #[serde(default)]
1231            settled_above: Vec<u64>,
1232        }
1233
1234        let order = Permutation::new(3, 500);
1235        let mut cursor = Cursor::walking(order);
1236        for position in order.iter().take(300) {
1237            cursor.settle(position);
1238        }
1239        cursor.settle(order.at(310).expect("inside the walk"));
1240
1241        let written = serde_json::to_string(&cursor.checkpoint()).expect("serializes");
1242        let older: Older = serde_json::from_str(&written).expect("an older reader reads it");
1243        let older = Checkpoint::new(older.watermark, older.settled_above);
1244
1245        assert!(older.settled_count() < cursor.settled_count());
1246        for position in 0..500 {
1247            assert!(
1248                !older.is_settled(position) || cursor.is_settled(position),
1249                "position {position} read as settled when it was not"
1250            );
1251        }
1252    }
1253
1254    /// A seeded scan settles out of order, so the watermark is correct whatever order
1255    /// positions arrive in.
1256    #[test]
1257    fn the_watermark_is_independent_of_arrival_order() {
1258        let forwards = {
1259            let mut cursor = Cursor::new();
1260            for position in 0..64 {
1261                cursor.settle(position);
1262            }
1263            cursor
1264        };
1265
1266        let backwards = {
1267            let mut cursor = Cursor::new();
1268            for position in (0..64).rev() {
1269                cursor.settle(position);
1270            }
1271            cursor
1272        };
1273
1274        let scattered = {
1275            let mut cursor = Cursor::new();
1276            for position in [7, 3, 63, 0, 1, 2, 4, 5, 6] {
1277                cursor.settle(position);
1278            }
1279            for position in 8..63 {
1280                cursor.settle(position);
1281            }
1282            cursor
1283        };
1284
1285        assert_eq!(forwards.watermark(), 64);
1286        assert_eq!(backwards.watermark(), 64);
1287        assert_eq!(scattered.watermark(), 64);
1288        assert_eq!(forwards, backwards);
1289        assert_eq!(forwards, scattered);
1290    }
1291
1292    /// A target reported twice does not move the watermark twice.
1293    #[test]
1294    fn settling_the_same_position_twice_is_idempotent() {
1295        let mut cursor = Cursor::new();
1296
1297        cursor.settle(0);
1298        cursor.settle(0);
1299        cursor.settle(0);
1300        assert_eq!(cursor.watermark(), 1);
1301
1302        cursor.settle(5);
1303        cursor.settle(5);
1304        assert_eq!(cursor.pending_count(), 1);
1305        assert_eq!(cursor.settled_count(), 2);
1306    }
1307
1308    /// A checkpoint round-trips through the cursor without moving.
1309    #[test]
1310    fn a_cursor_survives_a_checkpoint() {
1311        let mut cursor = Cursor::new();
1312        for position in [0, 1, 2, 9, 11, 12] {
1313            cursor.settle(position);
1314        }
1315
1316        let restored = Cursor::from_checkpoint(&cursor.checkpoint());
1317
1318        assert_eq!(restored, cursor);
1319        assert_eq!(restored.watermark(), 3);
1320        assert!(restored.is_settled(9));
1321        assert!(!restored.is_settled(3));
1322    }
1323
1324    /// A resumed scan asks about exactly what the first sitting did not settle, in the
1325    /// plan's own order.
1326    #[test]
1327    fn remaining_yields_only_what_was_not_settled() {
1328        let map = plan("192.0.2.1-192.0.2.4", "80,443");
1329        let all: Vec<Target> = map.iter().collect();
1330        assert_eq!(all.len(), 8, "four addresses on two ports");
1331
1332        let mut cursor = Cursor::new();
1333        for position in [0, 1, 2, 5] {
1334            cursor.settle(position);
1335        }
1336
1337        let remaining: Vec<PlannedTarget> = cursor.checkpoint().remaining(map.iter()).collect();
1338
1339        // The remaining targets still carry their positions in the whole plan.
1340        assert_eq!(
1341            remaining,
1342            vec![
1343                PlannedTarget::new(3, all[3]),
1344                PlannedTarget::new(4, all[4]),
1345                PlannedTarget::new(6, all[6]),
1346                PlannedTarget::new(7, all[7]),
1347            ]
1348        );
1349    }
1350
1351    /// A checkpoint that settled nothing re-asks the whole plan, and one that settled
1352    /// everything asks nothing.
1353    #[test]
1354    fn the_empty_and_complete_cases_are_both_exact() {
1355        let map = plan("192.0.2.1-192.0.2.4", "80,443");
1356        let total = map.iter().count();
1357
1358        let untouched = Cursor::new().checkpoint();
1359        assert_eq!(untouched.remaining(map.iter()).count(), total);
1360
1361        let mut finished = Cursor::new();
1362        for position in 0..total as u64 {
1363            finished.settle(position);
1364        }
1365        assert_eq!(finished.checkpoint().remaining(map.iter()).count(), 0);
1366        assert_eq!(finished.watermark(), total as u64);
1367    }
1368
1369    /// The cursor numbers targets by the same walk the dispatcher probes them by. The
1370    /// two live in different modules, and a divergence would resume a scan that skips the wrong
1371    /// targets.
1372    #[test]
1373    fn positions_follow_the_plans_own_enumeration() {
1374        let mut map = plan("192.0.2.1-192.0.2.2", "80,443");
1375        map.add_unit(TargetSet::new(
1376            "198.51.100.7".parse::<IpSet>().expect("a range"),
1377            "22".parse::<PortSet>().expect("ports"),
1378        ));
1379
1380        let once: Vec<Target> = map.iter().collect();
1381        let twice: Vec<Target> = map.iter().collect();
1382
1383        assert_eq!(once, twice, "the enumeration must be reproducible");
1384        assert_eq!(once.len(), 5, "two units, four targets then one");
1385        assert_eq!(
1386            once[4].ip,
1387            "198.51.100.7".parse::<std::net::IpAddr>().unwrap(),
1388            "units are walked in the order they were added"
1389        );
1390    }
1391
1392    /// The checkpoint reaches disk whole, comes back identical, and replacing it leaves
1393    /// no temporary file.
1394    #[cfg(feature = "journal-format")]
1395    #[test]
1396    fn a_checkpoint_round_trips_through_a_file() {
1397        let dir = std::env::temp_dir().join(format!(
1398            "zond-cursor-{}-{:?}",
1399            std::process::id(),
1400            std::thread::current().id()
1401        ));
1402        std::fs::create_dir_all(&dir).expect("scratch directory");
1403        let path = dir.join("cursor.json");
1404
1405        let mut cursor = Cursor::new();
1406        for position in [0, 1, 2, 9, 11, 12] {
1407            cursor.settle(position);
1408        }
1409
1410        cursor.checkpoint().write_atomically(&path).expect("writes");
1411        assert_eq!(Checkpoint::read(&path).expect("reads"), cursor.checkpoint());
1412
1413        // Written again over itself, as every checkpoint after the first is.
1414        cursor.settle(3);
1415        cursor
1416            .checkpoint()
1417            .write_atomically(&path)
1418            .expect("rewrites");
1419
1420        let reread = Checkpoint::read(&path).expect("rereads");
1421        assert_eq!(reread.watermark, 4);
1422        assert!(
1423            !dir.join("cursor.tmp").exists(),
1424            "the temporary file must not survive the rename"
1425        );
1426
1427        std::fs::remove_dir_all(&dir).ok();
1428    }
1429
1430    /// `is_settled` binary-searches, so the reader sorts a list that arrived unsorted.
1431    #[cfg(feature = "journal-format")]
1432    #[test]
1433    fn a_checkpoint_with_an_unsorted_list_is_sorted_on_read() {
1434        let dir = std::env::temp_dir().join(format!(
1435            "zond-cursor-unsorted-{}-{:?}",
1436            std::process::id(),
1437            std::thread::current().id()
1438        ));
1439        std::fs::create_dir_all(&dir).expect("scratch directory");
1440        let path = dir.join("cursor.json");
1441
1442        std::fs::write(&path, r#"{"watermark":2,"settled_above":[9,4,7,4]}"#).expect("writes");
1443
1444        let checkpoint = Checkpoint::read(&path).expect("reads");
1445
1446        assert_eq!(
1447            checkpoint.settled_above,
1448            vec![4, 7, 9],
1449            "sorted and deduped"
1450        );
1451        for position in [4, 7, 9] {
1452            assert!(checkpoint.is_settled(position), "{position} is in the file");
1453        }
1454        assert!(!checkpoint.is_settled(3));
1455
1456        std::fs::remove_dir_all(&dir).ok();
1457    }
1458
1459    /// A checkpoint naming positions below its own watermark normalises without
1460    /// double-counting.
1461    #[test]
1462    fn a_checkpoint_with_redundant_positions_normalises() {
1463        let checkpoint = Checkpoint {
1464            watermark: 5,
1465            settled_above: vec![1, 2, 5, 6],
1466            walked: None,
1467        };
1468
1469        let cursor = Cursor::from_checkpoint(&checkpoint);
1470
1471        assert_eq!(cursor.watermark(), 7, "5 and 6 are contiguous with 5");
1472        assert_eq!(cursor.pending_count(), 0);
1473        assert_eq!(cursor.settled_count(), 7);
1474    }
1475}