zond-engine 0.18.0

The core networking library powering Zond. Raw packet injection, protocol parsing, service and OS fingerprinting, and asynchronous network scanning.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
// Copyright (c) 2026 Erik Lening (hollowpointer) and Contributors
//
// This file is part of Zond Engine, licensed under the GNU Affero General
// Public License, version 3 or later. See the LICENSE file for details, or
// <https://www.gnu.org/licenses/agpl-3.0.html>.
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! # How many questions a scan may have outstanding
//!
//! A scan has to decide how hard to push, and the decision cannot be made in
//! advance. The right answer for a Linux server on a switch is thousands of
//! probes in flight; the right answer for the consumer router next to it is a
//! few dozen, and asking that router at the server's pace does not merely
//! annoy it: it manufactures findings. Probed faster than it will answer, a
//! router reports six hundred ports `filtered` with no more hesitation than it
//! reports the three that really are, and every one of those verdicts is a
//! claim about somebody's firewall that is actually a claim about our send rate.
//!
//! [`CongestionWindow`] makes the decision from evidence instead: it bounds how
//! many probes a scan may have outstanding, grows that bound while answers keep
//! arriving, and cuts it when the answers show the target is being outrun.
//!
//! ## Why a window and not a rate
//!
//! A configured rate is a guess, and it is wrong in both directions at once:
//! too fast for the router, too slow for the server, and no rate is right for a
//! scan that meets both. It is also unanchored: nothing about "four hundred
//! probes a second" refers to anything the target does.
//!
//! A window refers to exactly that. Probes leave as earlier ones are answered,
//! so the send rate settles at the rate the target is *resolving* them, whatever
//! that rate happens to be. It needs no clock, it needs no configuration, and it
//! is self-correcting: a target that slows down is asked more slowly without
//! anybody deciding anything.
//!
//! The engine still has a rate ceiling, and it still means something, but it is
//! a backstop against a defect in this file, not the thing that paces a scan.
//!
//! ## The loss signal, and why it is not the timeout
//!
//! TCP congestion control reduces on a timeout, because for TCP a lost segment
//! means a full queue. A port scanner cannot borrow that rule, because for a
//! scanner an unanswered probe usually means a firewall. Reducing on silence
//! would slow a scan to a crawl against exactly the hosts that are silent by
//! policy, and it would do it worst on the wide, heavily filtered ranges where
//! finishing at all is the whole difficulty.
//!
//! So the rule is narrower, and it turns on *who* is silent:
//!
//! > **Silence from a host that has never spoken is not congestion. Silence from
//! > a host that is otherwise answering us is.**
//!
//! A machine that replies to seven hundred probes and drops two hundred is not
//! running a two-hundred-port block list; it is failing to keep up. A machine
//! that replies to nothing is behind a firewall, or is not there, and asking it
//! more slowly discovers nothing at either, and neither is a machine that
//! replies to a port or two in a thousand, which is a firewall letting those
//! through. So a host is talking when it answers more than one probe in ten
//! of those put to it: read as talking on the strength of one open port, a
//! Windows machine behind its firewall held its scan at the window's floor.
//! That one distinction separates the cases a timeout-driven controller
//! confuses:
//!
//! | What is happening | What the controller sees | What it does |
//! |---|---|---|
//! | Host answers everything | Answers on the first ask | Grows to the ceiling |
//! | Address is a black hole | Nothing ever answers | Grows; finishes at speed |
//! | A firewall lets a port through | Answers, one in hundreds | Grows; finishes at speed |
//! | Host is being outrun | Timeouts, from a host that talks | Cuts the window |
//! | Host is being outrun badly | Answers arriving only on retries | Cuts the window |
//!
//! The last two are the same fault seen at different times, and both are needed.
//! A recovery is the stronger evidence, the port demonstrably wanted to answer,
//! but it arrives late, and it arrives *not at all* when the retries are lost as
//! well as the first attempt.
//!
//! ## What cutting only on recoveries costs, measured
//!
//! The obvious alternative cuts only on recoveries, on the reasoning that a
//! timeout might be a firewall. Measured against a Raspberry Pi on a home
//! network, a controller built that way never cut once, and three consecutive
//! scans of the same host reported this:
//!
//! - eleven ports were open across the three runs; **each run found exactly
//!   seven**, and only one port was found by all three;
//! - roughly two hundred and forty ports came back `filtered` each time, and the
//!   set was reshuffled every run: port 53 filtered once and open twice, port 22
//!   open twice and filtered once.
//!
//! Nothing on that host was filtered. Every one of those verdicts was the
//! scanner's own send rate, reported as somebody's firewall, which is precisely
//! the failure this module exists to prevent, arrived at by a different route.
//!
//! The arithmetic says why the recovery signal never fired. At a quarter of
//! probes lost and three *independent* attempts, an open port is missed one time
//! in seventy: eleven open ports should have come back as nearly eleven, not
//! seven. Seven means the attempts were not independent: all three of them fell
//! inside the same congested moment, so nothing was ever recovered on a retry and
//! the controller was handed no evidence at all. A signal that only fires once
//! the target has recovered is a signal that goes quiet exactly when the target
//! is worst off.
//!
//! ## When silence is itself the answer
//!
//! The rule above assumes a live stack answers every probe, so that silence
//! from a host that talks is a probe it dropped. That holds for a SYN, which
//! every port answers one way or the other, and not for a FIN, a NULL, an
//! Xmas or a Maimon probe, or a COOKIE-ECHO: an open port is required to
//! ignore those, so every open port on a host with closed ones is a timeout
//! from a host that is answering, on every attempt. Read as loss, a scan of
//! such a host cuts once per open port it finds and spends the run at its
//! floor, slowed by its own findings against a host that dropped nothing.
//!
//! Waiting for a retry to be answered instead is the rule the section above
//! measured failing, and it would fail the same way here: a closed port whose
//! every attempt fell inside one congested moment comes back as silent as an
//! open one. So one silence is not read either way, and what separates the
//! two is how much of it there is. An open port is the exception on a host,
//! a tenth of the ports asked on a service-dense one, while loss that retries
//! could not be counted on to recover was measured at a quarter. A scan whose
//! silence is a verdict weighs the one against the other: each silence from a
//! host that is answering counts five, each answer to a first ask takes one
//! back, and the window is cut once the balance stands twelve silences
//! past even. Five to one is the ratio of how much likelier a silence
//! and an answer are under a quarter lost than under a tenth open, so the
//! balance sinks while one outcome in ten is silent, climbs at one in four,
//! and holds still at one in six. A lone open port moves nothing; a host being
//! outrun still narrows the window, answered retries or not.
//!
//! A share averaged over the recent outcomes cannot draw that line. A silence
//! is heard a whole round-trip budget after it was asked and the answers
//! asked beside it at once, so outcomes reach the window with the silence
//! bunched: as many silences back to back as the window holds silent
//! questions, a whole window's worth after the scan loop wakes late. An
//! average over about a window's worth of outcomes reads each bunch as a
//! share of loss, and at one in ten it swings past a threshold anywhere near
//! it at the small windows its own cuts produce. The balance instead keeps
//! the credit answers earn for as long as the silences asked beside them can
//! still be on their way, five for each question in flight, so a bunch of
//! silence spends credit set aside for it and only silence beyond what was
//! asked reads as loss.
//!
//! ## What occupies the window
//!
//! A probe holds a slot **from its first send until its first outcome**, and its
//! first outcome is either an answer or the expiry of its round-trip budget.
//! After that it is in the retry schedule rather than in flight, and it holds
//! nothing.
//!
//! That line is not a detail; getting it wrong is the difference between a
//! working scanner and an unusable one. Hold the slot until the probe is
//! finally resolved and a firewalled port occupies the window for its whole
//! retry lifetime: most of two seconds, against a round trip of one
//! millisecond. A thousand filtered ports through a window of thirty-two is then
//! a minute of waiting for silence the scan had already heard, and the target
//! that is hardest to finish throttles the scan exactly as a congested one does.
//! Which is the confusion this whole module exists not to make.
//!
//! Retries are not readmitted. They are real packets and they count toward the
//! damping below, but a question already given up on once does not take a slot
//! back from a question nobody has asked yet.
//!
//! ## Growth, reduction and damping
//!
//! Growth is TCP's, because TCP's is right here: exponential while the window is
//! below [`WindowLimits::slow_start_threshold`], linear above it. Slow start is
//! what gets a scan up to speed in a handful of round trips instead of a
//! thousand; the threshold is what stops it overshooting a target's capacity by
//! a factor of two before it notices.
//!
//! A probe that timed out against a silent host grows the window exactly as an
//! answered one does. That reads backwards until the rule above is taken
//! seriously: nothing that host does is evidence about capacity, and asking it
//! more slowly discovers nothing. Against an address that answers nothing at all,
//! a firewalled host, a dead address in a range, this is what lets the scan
//! open up and finish, instead of creeping through at whatever window it
//! happened to start with.
//!
//! So every probe yields exactly one signal, and the caller decides which by
//! answering one question about it: did anything about this outcome say the
//! target is failing to keep up?
//!
//! Reduction halves, and then **refuses to halve again until the window's worth
//! of probes has been released**. Without that, one overloaded moment collapses
//! the window: a burst of fifty probes that all needed retries is fifty
//! recoveries arriving together, and fifty halvings is the floor. One reduction
//! per window of sends is the same rule TCP applies for the same reason, phrased
//! in probes rather than in round trips because a scanner already counts probes
//! and would have to invent the round trip.
//!
//! ## What is not a signal
//!
//! A frame the kernel's capture buffer dropped is loss too, and unlike a
//! timeout it is unambiguous: the reply arrived and this process was too busy
//! to take it. It is not wired in here, because it does not need to be: the
//! probe whose reply was dropped times out, is sent again, and is answered, and
//! that is a recovery like any other. Reading the counter as well would react
//! one round trip sooner and cost a poll in the receive loop for a case the
//! controller already handles. The counter is reported to the operator instead,
//! by [`ProbeAudit`](crate::scanner::audit::ProbeAudit), because a receive path
//! that cannot keep up is a fact about their machine rather than about the
//! network, and no amount of pacing makes that the right thing not to say.
//!
//! ## Where it applies, and where it does not
//!
//! TCP port scanning, where silence is exceptional and an answer is the norm.
//! Not UDP: a UDP probe's ordinary outcome *is* silence, and the ledger
//! cannot tell which attempt a reply answered because a UDP probe carries
//! nothing for the reply to echo. Both halves of the signal are missing, so a
//! UDP scan keeps a window that does not move, [`WindowLimits::fixed`], and
//! stays paced by the fixed rate its ICMP rate limiter demands. A controller fed
//! no evidence is not a conservative controller, it is a random one.

use crate::report::WindowSummary;

/// How much a silence that may be an open port weighs against an answer to a
/// first ask, in a scan whose silence is a verdict.
///
/// Five: a silence is two and a half times likelier from a host losing a
/// quarter of its probes, the share measured against a Raspberry Pi, than
/// from one with a tenth of its ports open, an answer one and a fifth times
/// likelier from the second, and five is the ratio of the logarithms of the
/// two. The balance
/// [`LOSS_EVIDENCE`] is compared against therefore holds still at one silence
/// in six. A host with more than one port in six open among those asked is
/// paced as a host losing probes, which costs the scan time and never a
/// verdict.
const SILENCE_WEIGHT: i64 = 5;

/// How far the balance of silence against answers has to climb before a scan
/// whose silence is a verdict reads it as loss.
///
/// Twelve silences past the balance. From a host with a tenth of its ports
/// open the balance reaches it by chance about once in a hundred thousand
/// first outcomes, more than one host's ports; from a host losing a quarter
/// of its probes it takes about a hundred.
const LOSS_EVIDENCE: i64 = 12 * SILENCE_WEIGHT;

/// The bounds a [`CongestionWindow`] moves within, and where it starts.
///
/// Declared per scanner beside its retry policy and deadline profile, since what
/// counts as a reasonable number of outstanding questions is a property of the
/// protocol and of what answers it.
///
/// `#[non_exhaustive]`, along with the three other pacing configurations, and
/// for the reason they share: these are the knobs a controller gains a field of
/// every time somebody measures something new, this module having recorded
/// three such measurements already, and every one of them is read here rather
/// than pattern-matched by a consumer. Closing the literal costs a caller
/// [`new`](Self::new) instead of a struct expression, and it is what keeps
/// [`new`](Self::new)'s bounds check from being walked around.
#[non_exhaustive]
#[derive(Debug, Clone, Copy)]
pub struct WindowLimits {
    /// The window before anything has been learned.
    ///
    /// Not one. A scan that begins with a single outstanding probe spends a
    /// round trip per doubling to reach a useful size, and on a local segment
    /// that is most of the scan. Every stack in service will answer a few dozen
    /// simultaneous probes, so starting there costs nothing and saves several
    /// round trips of ramp.
    pub initial: u32,
    /// The smallest window a reduction may reach. Below this a scan stops making
    /// progress rather than merely being polite.
    pub floor: u32,
    /// The largest window growth may reach, whatever the evidence.
    ///
    /// It bounds correlation state as much as traffic: every outstanding probe
    /// is a ledger entry and a timer, and a scan waiting on more answers than
    /// this is not getting them sooner.
    pub ceiling: u32,
    /// Where exponential growth gives way to linear.
    ///
    /// Slow start doubles the window every round trip, which is how a scan
    /// reaches useful speed quickly and also how it sails past a target's
    /// capacity before the first recovery arrives to say so. The threshold is
    /// the size past which the scan stops guessing upward and starts creeping.
    pub slow_start_threshold: u32,
}

impl WindowLimits {
    /// Bounds counted in probes: the window opens at `initial`, is never cut
    /// below `floor` or grown past `ceiling`, and doubles only while it is
    /// under `slow_start_threshold`.
    pub const fn new(initial: u32, floor: u32, ceiling: u32, slow_start_threshold: u32) -> Self {
        Self {
            initial,
            floor,
            ceiling,
            slow_start_threshold,
        }
    }

    /// A window that does not move, for a scan whose protocol offers no evidence
    /// to move it on.
    ///
    /// Not a disabled feature: it is the correct configuration for UDP, where
    /// silence is the ordinary outcome and no reply names the attempt it
    /// answers. See the module documentation.
    pub const fn fixed(capacity: u32) -> Self {
        Self {
            initial: capacity,
            floor: capacity,
            ceiling: capacity,
            slow_start_threshold: capacity,
        }
    }

    /// Whether this window can move at all.
    const fn adaptive(&self) -> bool {
        self.floor < self.ceiling
    }
}

/// How many probes a scan may keep outstanding, adapted to what the targets are
/// managing to answer.
///
/// A scanner reads [`capacity`](Self::capacity) to decide whether to admit
/// another target, and reports three things back: that a probe was sent, that
/// one was answered, and that one was answered *only after being sent again*.
/// The last is the loss signal and the reason this type can tell a slow host
/// apart from a firewalled one; the module documentation has the argument.
#[derive(Debug, Clone)]
pub struct CongestionWindow {
    limits: WindowLimits,
    /// Fractional, so linear growth can add a fraction of a probe per answer and
    /// arrive at one probe per window rather than rounding to nothing.
    window: f64,
    threshold: f64,
    /// Questions currently awaiting an answer: sent, and neither answered nor
    /// yet out of round-trip budget. What [`capacity`](Self::capacity) bounds.
    in_flight: u32,
    /// Probes released since the last reduction, against which
    /// [`epoch`](Self::epoch) is compared.
    since_reduction: u32,
    /// How many probes must be released before another reduction is allowed:
    /// the window as it stood when the last one happened.
    epoch: u32,
    peak: usize,
    reductions: u32,
    /// The balance of silence that may be a verdict against answers, among
    /// first outcomes from answering hosts: up [`SILENCE_WEIGHT`] for each
    /// silence, down one for each answer, and never below the credit the
    /// questions still in flight may spend. What
    /// [`record_ambiguous_silence`](Self::record_ambiguous_silence) compares
    /// against [`LOSS_EVIDENCE`].
    silence_evidence: i64,
    /// Whether the scan has admitted its last question. See
    /// [`stop_admitting`](Self::stop_admitting).
    admission_over: bool,
}

impl CongestionWindow {
    /// A window at its starting size, with nothing learned yet.
    ///
    /// Bounds that disagree do not panic. `floor` and `ceiling` are adjacent
    /// arguments of one type, so a caller can cross them; the floor wins, for the reason
    /// [`suggest_timeout`](super::rtt_window::RttWindow::suggest_timeout) and
    /// [`ProbeLedger`](super::retry::ProbeLedger) give. A crossed pair then
    /// describes a range with nothing in it, so the window is stationary and
    /// reports itself as such through [`WindowSummary::adaptive`]. `u32::clamp`
    /// asserts instead, and would take the scan down before that logic could
    /// run.
    pub fn new(limits: WindowLimits) -> Self {
        let window = f64::from(
            limits
                .initial
                .clamp(limits.floor, limits.ceiling.max(limits.floor)),
        );
        Self {
            limits,
            window,
            threshold: f64::from(limits.slow_start_threshold),
            in_flight: 0,
            since_reduction: 0,
            // Zero, so the first recovery is acted on rather than damped. The
            // damping exists to stop one bad moment being counted many times,
            // not to ignore the first evidence a scan ever gets.
            epoch: 0,
            peak: window as usize,
            reductions: 0,
            silence_evidence: 0,
            admission_over: false,
        }
    }

    /// The most questions that may be awaiting an answer right now.
    ///
    /// Never zero: a window that admits nothing is a scan that cannot make
    /// progress, and the floor is what a reduction is allowed to reach rather
    /// than a value it may pass through.
    pub fn capacity(&self) -> usize {
        (self.window as usize).max(1)
    }

    /// How many questions are awaiting an answer.
    pub fn in_flight(&self) -> usize {
        self.in_flight as usize
    }

    /// Whether another question may be asked.
    pub fn has_room(&self) -> bool {
        self.in_flight() < self.capacity()
    }

    /// Records a first attempt leaving the wire: it takes a slot, and it counts
    /// toward the damping.
    pub fn record_send(&mut self) {
        self.in_flight = self.in_flight.saturating_add(1);
        self.since_reduction = self.since_reduction.saturating_add(1);
    }

    /// Records a retry leaving the wire: it counts toward the damping and takes
    /// no slot.
    ///
    /// It is real traffic, so the damping has to see it: the window's worth of
    /// sends between reductions is a count of packets, not of targets. It takes
    /// no slot because the slot was released when the question it repeats ran
    /// out of round-trip budget; see the module documentation on what occupies
    /// the window.
    pub fn record_resend(&mut self) {
        self.since_reduction = self.since_reduction.saturating_add(1);
    }

    /// Releases the slot one question was holding.
    ///
    /// Separate from the two signals below, and it has to be: a question can end
    /// in a way that says the target is struggling (a timeout from a host that
    /// is otherwise answering) or in a way that says nothing (silence from a
    /// host that answers nothing), and both free the slot. Folding the release
    /// into either signal would mean the other one leaked.
    ///
    /// Call it exactly once per question, on whichever event ends it first: an
    /// answer, or the expiry of its round-trip budget. Never on a retry: the
    /// slot went back when the question the retry repeats ran out of budget.
    pub fn release(&mut self) {
        self.in_flight = self.in_flight.saturating_sub(1);
    }

    /// Records a question answered on its first ask: the target is keeping up.
    ///
    /// Grows the window, and weighs against silence in the balance
    /// [`record_ambiguous_silence`](Self::record_ambiguous_silence) reads.
    pub(crate) fn record_answer(&mut self) {
        self.observe_first_outcome(false);
        self.record_progress();
    }

    /// Records silence from a host that is answering, in a scan where every
    /// port would have answered: a probe the target dropped.
    ///
    /// Cuts the window, while the scan still has questions to admit, for the
    /// reason [`stop_admitting`](Self::stop_admitting) gives.
    pub(crate) fn record_loss(&mut self) {
        if !self.admission_over {
            self.record_congestion();
        }
    }

    /// Records silence from a host that is answering, in a scan where silence
    /// is also what an open port gives: an open port found, or a probe lost,
    /// and nothing about this one outcome says which.
    ///
    /// Neither grows the window nor cuts it on its own. It cuts once the
    /// balance of silence against answers passes [`LOSS_EVIDENCE`], which a
    /// host's open ports do not reach and a host being outrun does. See the
    /// module documentation.
    ///
    /// Read only while the scan still has questions to admit; see
    /// [`stop_admitting`](Self::stop_admitting).
    pub(crate) fn record_ambiguous_silence(&mut self) {
        if !self.admission_over && self.observe_first_outcome(true) > LOSS_EVIDENCE {
            self.record_congestion();
        }
    }

    /// Records that the scan has admitted its last question, so the window
    /// paces nothing from here and silence is no longer read as loss, one
    /// timeout at a time or as a balance.
    ///
    /// A cut from here would slow nothing, and the outcomes still owed are
    /// whatever was left in flight, where silence is over-represented by
    /// construction: an answered question gives its slot back after a round
    /// trip and a silent one after its whole budget, so a window at work holds
    /// mostly silent questions however few of the questions asked were
    /// silent. Weighed as evidence, they could cut a window that paces
    /// nothing, on a host that dropped nothing, and leave it reported at its
    /// floor.
    pub(crate) fn stop_admitting(&mut self) {
        self.admission_over = true;
    }

    /// Folds one first outcome from an answering host into the balance of
    /// silence against answers, and returns the balance.
    ///
    /// Held above [`credit_in_flight`](Self::credit_in_flight), so a run of
    /// clean answers early in a long scan cannot bank enough to hide loss that
    /// starts late in it: the credit kept is what the silences still on their
    /// way may need, and nothing more.
    fn observe_first_outcome(&mut self, silent: bool) -> i64 {
        let step = if silent { SILENCE_WEIGHT } else { -1 };
        self.silence_evidence = (self.silence_evidence + step).max(self.credit_in_flight());
        self.silence_evidence
    }

    /// The lowest the balance of silence may sink: the weight of one silence
    /// for every question still in flight, negated.
    ///
    /// Each question in flight is one whose outcome is still to come, and
    /// every one of them may yet be heard as silence. Their answering
    /// neighbours were heard a round-trip budget earlier, so the credit those
    /// earned has to be kept until the silences it balances arrive, and no
    /// more than those silences can spend.
    fn credit_in_flight(&self) -> i64 {
        -SILENCE_WEIGHT * i64::from(self.in_flight)
    }

    /// Records an outcome that carried no sign of the target failing to keep up:
    /// answered on the first ask, or silence from a host that answers nothing
    /// anyway.
    ///
    /// Grows the window. See the module documentation for why the second of
    /// those grows it rather than shrinking it.
    pub fn record_progress(&mut self) {
        if !self.limits.adaptive() {
            return;
        }

        let step = if self.window < self.threshold {
            1.0
        } else {
            1.0 / self.window
        };
        self.window = (self.window + step).min(f64::from(self.limits.ceiling));
        self.peak = self.peak.max(self.capacity());
    }

    /// Records an outcome that says the target is being asked faster than it can
    /// answer: a question it dropped while answering others, or one it answered
    /// only after being asked again.
    ///
    /// Halves the window, then refuses to halve again until that many probes
    /// have been released. The balance of silence starts over with it, at the
    /// credit the questions still in flight may spend: they were asked at the
    /// pace just cut, and the silence among them is not evidence for the next
    /// cut, which has to be earned at the pace this one set.
    pub fn record_congestion(&mut self) {
        if !self.limits.adaptive() || self.since_reduction < self.epoch {
            return;
        }

        self.threshold = (self.window / 2.0).max(f64::from(self.limits.floor));
        self.window = self.threshold;
        self.epoch = self.capacity() as u32;
        self.since_reduction = 0;
        self.reductions = self.reductions.saturating_add(1);
        self.silence_evidence = self.credit_in_flight();
    }

    /// Releases every slot still held, for a scan that is stopping before its
    /// outstanding questions could be settled on their own.
    pub fn release_all(&mut self) {
        self.in_flight = 0;
    }

    /// What this window did over the run, for the audit line.
    pub fn summary(&self) -> WindowSummary {
        WindowSummary {
            capacity: self.capacity(),
            peak: self.peak,
            reductions: self.reductions,
            adaptive: self.limits.adaptive(),
            at_floor: self.limits.adaptive() && self.capacity() <= self.limits.floor as usize,
        }
    }
}

// ╔════════════════════════════════════════════╗
// ║ ████████╗███████╗███████╗████████╗███████╗ ║
// ║ ╚══██╔══╝██╔════╝██╔════╝╚══██╔══╝██╔════╝ ║
// ║    ██║   █████╗  ███████╗   ██║   ███████╗ ║
// ║    ██║   ██╔══╝  ╚════██║   ██║   ╚════██║ ║
// ║    ██║   ███████╗███████║   ██║   ███████║ ║
// ║    ╚═╝   ╚══════╝╚══════╝   ╚═╝   ╚══════╝ ║
// ╚════════════════════════════════════════════╝

#[cfg(test)]
mod tests {

    /// `floor` and `ceiling` are adjacent `u32`s on the constructor, so a
    /// caller can cross them. `u32::clamp` asserts, which would turn that into
    /// a panic in the scanning process, two lines before the `adaptive` check
    /// that already handles a range with nothing in it.
    #[test]
    fn crossed_bounds_freeze_the_window_rather_than_panicking() {
        let window = CongestionWindow::new(WindowLimits::new(10, 100, 50, 20));

        assert_eq!(window.capacity(), 100, "the floor wins");
        assert!(
            !window.summary().adaptive,
            "and a range with nothing in it cannot move"
        );
    }

    /// Growth and reduction are both no-ops on such a window, so nothing
    /// downstream has to know the bounds were crossed.
    #[test]
    fn a_frozen_window_neither_grows_nor_cuts() {
        let mut window = CongestionWindow::new(WindowLimits::new(10, 100, 50, 20));
        let before = window.capacity();

        window.record_send();
        window.record_progress();
        window.record_congestion();

        assert_eq!(window.capacity(), before);
        assert_eq!(window.summary().reductions, 0);
    }
    use super::*;

    fn limits() -> WindowLimits {
        WindowLimits::new(16, 4, 512, 64)
    }

    /// Below the threshold the window doubles per round trip's worth of
    /// answers, which is what gets a scan up to speed in a handful of round
    /// trips rather than a thousand.
    #[test]
    fn slow_start_doubles_the_window_every_round_trip() {
        let mut window = CongestionWindow::new(limits());
        assert_eq!(window.capacity(), 16);

        // One round trip: every outstanding probe answered.
        for _ in 0..16 {
            window.record_progress();
        }
        assert_eq!(window.capacity(), 32);

        for _ in 0..32 {
            window.record_progress();
        }
        assert_eq!(window.capacity(), 64);
    }

    /// Past the threshold it creeps instead, so a scan that has found a target's
    /// working pace does not immediately overshoot it again.
    ///
    /// Eight round trips' worth of answers buy eight more probes rather than
    /// eight doublings: the same eight round trips of slow start would have
    /// asked for sixteen thousand.
    #[test]
    fn past_the_threshold_the_window_grows_by_one_per_round_trip() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 4096, 64));
        assert_eq!(window.capacity(), 64);

        for _ in 0..(8 * 64) {
            window.record_progress();
        }

        assert_eq!(
            window.capacity(),
            71,
            "eight round trips of linear growth, less the rounding that adding \
             one over a window at a time costs"
        );
    }

    /// The reason this type exists. A halving per recovery would collapse the
    /// window on the first overloaded moment, because one burst that needed
    /// retries produces a burst of recoveries, and the scan would then crawl
    /// against a host that was merely busy for a millisecond.
    #[test]
    fn one_overloaded_moment_cuts_the_window_once_and_not_fifty_times() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 512));
        assert_eq!(window.capacity(), 64);

        for _ in 0..50 {
            window.record_congestion();
        }

        assert_eq!(window.capacity(), 32, "halved, and only once");
        assert_eq!(window.summary().reductions, 1);
    }

    /// The damping lifts once the window's worth of probes has gone out, so a
    /// target that is still being outrun is still cut back.
    #[test]
    fn a_second_window_of_probes_earns_a_second_reduction() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 512));
        window.record_congestion();
        assert_eq!(window.capacity(), 32);

        for _ in 0..32 {
            window.record_send();
        }
        window.record_congestion();

        assert_eq!(window.capacity(), 16);
        assert_eq!(window.summary().reductions, 2);
    }

    /// A reduction stops at the floor. Past it a scan is not being polite, it is
    /// failing to finish, and the verdicts it does not reach are indeterminate
    /// rather than merely late.
    #[test]
    fn reduction_stops_at_the_floor() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 8, 512, 512));

        for _ in 0..20 {
            window.record_congestion();
            for _ in 0..64 {
                window.record_send();
            }
        }

        assert_eq!(window.capacity(), 8);
    }

    /// Growth stops at the ceiling, which bounds correlation state as much as
    /// traffic: a scan waiting on more answers than this is not getting them
    /// sooner.
    #[test]
    fn growth_stops_at_the_ceiling() {
        let mut window = CongestionWindow::new(WindowLimits::new(16, 4, 32, 1024));

        for _ in 0..1000 {
            window.record_progress();
        }

        assert_eq!(window.capacity(), 32);
        assert_eq!(window.summary().peak, 32);
    }

    /// The rule the whole controller turns on: a question stops occupying the
    /// window the moment it is settled, and running out of round-trip budget is
    /// a settlement.
    ///
    /// Held instead until the probe was finally retired, a firewalled port would
    /// occupy a slot for its whole retry lifetime, most of two seconds against
    /// a round trip of one millisecond, and a thousand of them through a small
    /// window is a minute of waiting for silence the scan had already heard.
    #[test]
    fn silence_frees_the_slot_it_was_holding() {
        let mut window = CongestionWindow::new(WindowLimits::new(4, 2, 512, 512));

        for _ in 0..4 {
            window.record_send();
        }
        assert!(!window.has_room(), "the window is full of open questions");

        window.release();
        window.record_progress();
        assert!(
            window.has_room(),
            "and one of them has now been answered by silence"
        );
        assert!(
            window.capacity() > 4,
            "which is not congestion, so the window opens rather than closing"
        );
    }

    /// A retry is traffic and the damping has to count it, but it is a repeat of
    /// a question already given up on, so it must not take a slot back from a
    /// question nobody has asked yet.
    #[test]
    fn a_retry_costs_no_slot() {
        let mut window = CongestionWindow::new(WindowLimits::new(4, 2, 512, 512));

        window.record_send();
        window.release();
        assert_eq!(window.in_flight(), 0);

        window.record_resend();
        assert_eq!(window.in_flight(), 0, "the slot went back at the timeout");
    }

    /// An answer that arrived only on a repeat frees nothing, because the slot
    /// went back when the first attempt timed out. Freeing it twice would let
    /// the window admit more than it believes it has.
    #[test]
    fn a_recovery_does_not_free_a_second_slot() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 512));

        window.record_send();
        window.release();
        window.record_resend();
        window.record_congestion();

        assert_eq!(window.in_flight(), 0);
    }

    /// A UDP scan has neither half of the signal, silence is its ordinary
    /// outcome and its replies name no attempt, so its window is told to hold
    /// still, and nothing it is fed may move it.
    #[test]
    fn a_fixed_window_ignores_every_signal() {
        let mut window = CongestionWindow::new(WindowLimits::fixed(64));

        for _ in 0..100 {
            window.record_progress();
            window.record_congestion();
            window.record_send();
        }

        assert_eq!(window.capacity(), 64);
        assert_eq!(window.summary().reductions, 0);
        assert!(!window.summary().adaptive);
    }

    /// A silence that may be an open port neither opens the window nor closes
    /// it while it is the exception among a host's answers: a scan whose silence
    /// is a verdict meets one on every host with services.
    #[test]
    fn an_occasional_ambiguous_silence_among_answers_moves_nothing() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));

        for outcome in 0..(64 * 20) {
            if outcome % 20 == 0 {
                window.record_ambiguous_silence();
            } else {
                window.record_answer();
            }
        }

        assert_eq!(window.summary().reductions, 0, "one in twenty is not loss");
    }

    /// One silence in ten, the open ports of a service-dense host, is still
    /// not loss, and nothing about how the silences fall among the answers
    /// may make it so over a scan of a few thousand ports.
    #[test]
    fn a_tenth_of_first_outcomes_silent_is_not_loss() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));
        // A fixed scramble, so the silences fall unevenly, some back to back,
        // and the test sees the same run every time.
        let mut state: u64 = 0x2545_f491_4f6c_dd1d;

        for _ in 0..(64 * 50) {
            state = state
                .wrapping_mul(6_364_136_223_846_793_005)
                .wrapping_add(1_442_695_040_888_963_407);
            if (state >> 33).is_multiple_of(10) {
                window.record_ambiguous_silence();
            } else {
                window.record_answer();
            }
        }

        assert_eq!(window.summary().reductions, 0, "one in ten is not loss");
    }

    /// A silence is heard a whole budget after it was asked and the answers
    /// asked beside it at once, so silences reach the window back to back, a
    /// window's worth at a time when the loop wakes late. The credit kept for
    /// the questions in flight is what stops such a bunch reading as loss.
    ///
    /// Here each round asks sixty-four questions, six of them silent, and the
    /// silences of eight rounds are heard together: forty-eight silences with
    /// no answer between them, which any share of recent outcomes would read
    /// as a host dropping most of what it is asked.
    #[test]
    fn silence_heard_bunched_behind_its_answers_is_not_loss() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));

        for round in 1..=64u32 {
            for _ in 0..64 {
                window.record_send();
            }
            for _ in 0..58 {
                window.release();
                window.record_answer();
            }
            if round.is_multiple_of(8) {
                for _ in 0..(6 * 8) {
                    window.release();
                    window.record_ambiguous_silence();
                }
            }
        }

        assert_eq!(window.summary().reductions, 0, "{:?}", window.summary());
    }

    /// Silence at a share no set of open ports plausibly accounts for is loss,
    /// bunched or not, and it cuts although no retry was ever answered to prove
    /// it. One in four, heard in the same bunches as above.
    #[test]
    fn ambiguous_silence_at_a_share_of_loss_cuts_the_window() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));

        for round in 1..=16u32 {
            for _ in 0..64 {
                window.record_send();
            }
            for _ in 0..48 {
                window.release();
                window.record_answer();
            }
            if round.is_multiple_of(4) {
                for _ in 0..(16 * 4) {
                    window.release();
                    window.record_ambiguous_silence();
                }
            }
        }

        assert!(window.summary().reductions > 0, "one in four is loss");
        assert!(window.capacity() < 64);
    }

    /// Once the last question is admitted, what is left in flight is mostly
    /// silence however little of what was asked was silent, since a silent
    /// question holds its slot for a whole budget. Those arrive in a run with
    /// no answers between them, and must not be weighed as loss.
    #[test]
    fn silence_left_in_flight_after_the_last_admission_is_not_weighed_as_loss() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));
        for _ in 0..(64 * 4) {
            window.record_answer();
        }

        window.stop_admitting();
        for _ in 0..64 {
            window.record_ambiguous_silence();
        }

        assert_eq!(window.summary().reductions, 0);
    }

    /// A dropped probe heard after the last question went out is weighed as
    /// the balance above is not: a cut from there slows nothing, and the
    /// probes still in flight are mostly the silent ones, so one filtered
    /// port asked late would leave the window reported at its floor and the
    /// scan read as outrun.
    #[test]
    fn a_dropped_probe_heard_after_the_last_admission_does_not_cut() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));

        window.stop_admitting();
        window.record_loss();
        assert_eq!(window.summary().reductions, 0, "nothing left to pace");

        let mut admitting = CongestionWindow::new(WindowLimits::new(64, 4, 512, 64));
        admitting.record_loss();
        assert_eq!(
            admitting.summary().reductions,
            1,
            "while admitting, it cuts"
        );
    }

    /// After a cut, the window has to be able to climb back: a target that was
    /// briefly busy is not a target that must be asked slowly forever.
    ///
    /// It climbs back *linearly*, and that is the point of moving the threshold
    /// down with the window rather than leaving it where it was. A scan that
    /// re-entered slow start after every cut would double straight back into the
    /// capacity it had just been told it exceeded.
    #[test]
    fn a_window_that_was_cut_climbs_back_slowly_rather_than_doubling() {
        let mut window = CongestionWindow::new(WindowLimits::new(64, 4, 512, 512));
        window.record_congestion();
        assert_eq!(window.capacity(), 32);

        for _ in 0..(2 * 32) {
            window.record_progress();
        }

        assert_eq!(
            window.capacity(),
            33,
            "two round trips buy two probes, not two doublings"
        );
    }
}