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}